题目大意就不展开了
分析
排序,但用 必定会超时。设选手分数为我们观察到 的范围为 ,比较小,考虑用桶排序。用 记录分数为 的选手的个数。
对于每次输入 ,都使 。到第 个人时的分数线为 ( 表示向下取整,在 类型中结果会自动向下取整)。当每次查询时只用从 到 遍历一遍数组 即可,但注意 循环的结束条件是 ,因为 循环结束后 会多减去 次,所以答案 要加 。
AC代码
#include <bits/stdc++.h>
using namespace std;
int n, w, a[601], len = 0, ans[100001];
int main() {
freopen("live.in", "r", stdin);
freopen("live.out", "w", stdout);
scanf("%d %d", &n, &w);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
a[x]++;
int p = max(1, i * w / 100);
int sum = 0;
int j;
for (j = 600; j >= 0 && sum < p; j--) {
sum += a[j];
}
ans[i] = j + 1; //循环结束时j多减了1,要加回来
}
for (int i = 1; i <= n; ++i) {
printf("%d ", ans[i]);
}
return 0;
}