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