题解 P7072 【直播获奖（暂无数据）】

· · 题解

还是得说，今年的第二题也比去年难。

去年第二道和今年第二道都是模拟，但是今年更富有技巧性

题目大意：先给出参赛人数和获奖几率，每次会导入一个成绩，算出导入成绩后获奖分数线。

拿到题一开始，应该会想到一个会超时的算法：
先算出获奖人数，即max(1,floor(p * w%)
然后一一计算，通过sort排序算出分数线。
当然，这个方法拿不了满，在这里只是提及一下。

下面说一个可以得到满分的方法：
我们开一个数组k[605]来记录每个分数的人数，最终从高往低循环，以此将此分数的人数减掉。

上一个考场程序。


#include <bits/stdc++.h>
using namespace std;

const int Maxn=1e5+5;
int a[Maxn],b[605];

int main()       
{
    int n,per;        
    cin>>n>>per;      
    for (int i=1;i<=n;++i)
        cin>>a[i];  

    for (int i=1;i<=n;++i){
        int mn=max(1.00,floor(i*per*1.0/100));
        if (i==1){
            cout<<a[1]<<" ";
            b[a[1]]++;
        }
        else{
            b[a[i]]++;
            for (int i=600;i>=0;--i){
                mn=mn-b[i];
                if (mn<=0){
                    cout<<i<<" ";
                    break;  
                }
            }
        }
    }

    return 0;
}