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

GZXUEXUE · 2024-12-26 13:28:43 · 题解

思路

注意到由于选手的分数不超过 600，且并列的人都可以获奖，考虑使用一个数组去记录该得分段的人数。

每次加入一个人之后，我们只需要找到一条分数线，判断当前累计获奖人数是否达到了 \max(1, \lfloor p \times w \%\rfloor) 即可。同时，由于计算分数线不用考虑后面的人，所以可以直接一边输入一遍计算。

该算法的时间复杂度为 O(nm)，其中 m = 600。

实现

# include <iostream>
# include <cmath>
using namespace std;
int a[601]; // a[i]表示该分数段的人数
int main(){
    int n,w,tmp; scanf("%d %d",&n,&w);
    for (int i = 0;i < n;i++){
        cin >> tmp;
        a[tmp]++; // 记录这个人的分数
        // j表示当前分数线，sum表示当前累计获奖人数，sc表示当前计划获奖人数
        int j = 600,sum = 0,sc = max((i + 1) * w / 100,1);
        for (;j >= 0 && sum < sc;j--) sum += a[j];
        cout << ++j << " ";
    }return 0;
}