计数排序

#include <iostream>
#include <vector>
using namespace std;

//核心要求
//实时计算：每评出一个选手成绩，就要计算当前的获奖分数线
//获奖人数：k = max(1, ⌊p × w / 100⌋)，其中 p 是当前已评出的人数
//分数线：获奖选手中的最低成绩（考虑并列情况）
//关键点
//并列处理：如果第 k 名有多个选手并列，他们都能获奖
//实时性：需要依次输出 n 个时刻的分数线

//由于成绩范围很小（0-600），可以用计数排序优化
int main() {
    
    int n, w;
    cin >> n >> w;
    
    // cnt[score] 记录成绩为 score 的人数
    vector<int> cnt(601, 0);
    
    for (int p = 1; p <= n; p++) {
        int score;
        cin >> score;
        cnt[score]++;
        
        // 计算计划获奖人数
        int k = max(1, p * w / 100);
        
        // 从高到低累加人数，找到第 k 名的成绩
        int sum = 0;
        for (int s = 600; s >= 0; s--) {
            sum += cnt[s];
            if (sum >= k) {
                cout << s;
                break;
            }
        }
        
        if (p < n) cout << ' ';
        else cout << '\n';
    }
    
    return 0;
}