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

思路

注意到由于选手的分数不超过

600

，且并列的人都可以获奖，考虑使用一个数组去记录该得分段的人数。

每次加入一个人之后，我们只需要找到一条分数线，判断当前累计获奖人数是否达到了

\max(1, \lfloor p \times w \%\rfloor)

即可。同时，由于计算分数线不用考虑后面的人，所以可以直接一边输入一遍计算。

该算法的时间复杂度为

O(nm)

，其中

m = 600

。

实现

CPP

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

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

文章操作

思路

实现

相关推荐

评论

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