P7072 [CSP-J2020] 直播获奖 题解

暴力

使用 $\Theta (n^2)$ 的时间复杂度来解决这题大约能拿到 $60pts$.

即枚举 $p$，再枚举每个选手的分数.

正解

桶是个好东西.我们开一个桶，记录当前分数有多少人.

然后计算获奖人数，分数从大到小进行枚举，直到当前人数 $\ge$ 获奖人数.

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>

using namespace std;

int n, w, t, c[603];

int main() {
	scanf("%d%d", &n, &w);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &t);
		c[t]++; // 当分数为 t 时的人数
		int sum = 0;
		for (int j = 600; j >= 0; j--) { // 从大到小枚举
			if (c[j]) { // 当前分数有人
				sum += c[j]; // 加上人数
				if (sum >= max(1, i * w / 100)) { // 到达边界
					printf("%d ", j); // 输出分数线
					break; // 退出循环.
				}
			}
		}
	}
	return 0;
}