Problem
考查知识点：桶优化。
题目简述
竞赛的获奖率为 \(w\%\)，即当前排名前 \(w\%\) 的选手的最低成绩就是即时的分数线。
若当前已评出了 \(p\) 个选手的成绩，则当前计划获奖人数为 \(\max(1, \lfloor p \times w \%\rfloor)\)，如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
求：每个选手的成绩读入后，逐一输出当时实时的获奖分数线。
暴力解法
每读入一个选手的成绩，计算出计划获奖人数 \(p\) ，然后 \(sort\)，输出前 \(a_p\)。
时间复杂度估算：
\(O(n \times n \log n)\)，显然达到了 \(10^{10}\)。
考虑优化
关键在排序的地方。这道题，数据范围中提到了
"对于所有测试点，每个选手的成绩均为不超过 \(600\) 的非负整数"
这就给我们一个启发：可以用桶排序！
思路整理
设 \(cnt\) 数组为每个数出现的次数。
每次读入成绩 $x $，cnt[x]++，然后计算出获奖人数 \(p\)，从最大数值 \(600\) 循环到 \(0\)，当数到 \(p\) 人的时候，输出下标。
代码
#include <iostream>
#include <map>
using namespace std;
int n,w;
int x,c[610],cnt;
int main() {
cin >> n >> w;
for (int i = 1;i <= n;i++) {
scanf("%d",&x);
c[x]++;
cnt = 0;
int k = max(1,(int)w * i / 100);
for (int j = 600;j >= 0;j--) {
if (cnt + c[j] < k) {
cnt += c[j];
} else {
printf("%d ",j);
break;
}
}
}
return 0;
}