P7072 [CSP-J2020] 直播获奖

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;
}