题解 P7072 【直播获奖（民间数据）】

· · 题解

好题，好题！（结果看了别人的题解还发现我可能想得太复杂了……）

设当前有i个人评出成绩时获奖分数线为第k人的分数，因为需要输出每个k所对应的值，所以需要加入一个数就自动排序，很自然就能想到优先队列

那这个问题就变成了对每个i求最大k个数的最小值，建立一个小根堆，如果此时堆里的数据还不够k个，则加入一个新数据；如果已经够了k个，则要考虑一下需不需要进行数据替换。

那么新数据的选择是一个很关键的问题。一开始我下意识地将新读入的第i个数据直接加入小根堆，但手推了一遍样例1之后发现，有可能之前已经被踢出小根堆的数据会比当前新读入的第i个数据来得要优，此时如果选择新读入的第i个数据加入小根堆的话就会出错。

考虑到这一点，可以建立一个大根堆，用于保存当前不是前k大的数，新输入的数据直接加入大根堆。如果当前用于统计前k大的数的小根堆里，元素的个数还不足k个时，直接取大根堆的堆顶加入小根堆即可；如果此时元素的个数已经够了k个，则要考虑新加入的数据是否会产生影响，即比较大根堆和小根堆的堆顶，如果此时小根堆的堆顶<大根堆的堆顶，则交换。对于两个相邻的i来说，k的最大变化量只能为1，所以只处理堆顶元素就好。

还有个坑就是确定k值，谁能想到我因为向下取整连着三种做法都wa连个点

代码如下

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

priority_queue <int,vector<int>,greater<int> > a;
priority_queue <int,vector<int>,less<int> > b;
int n,p;

int main(){
    cin >> n >> p;
    for (int i=1;i<=n;i++){
        int tot=p*i/100;
        tot=max(1,tot);
        //cout << tot << endl;
        int temp;
        cin >> temp;
        b.push(temp);
        if (a.size()<tot){
            a.push(b.top());
            b.pop();
        }
        else{
            if (a.top()<b.top()){
                a.push(b.top());
                b.pop();
                b.push(a.top());
                a.pop();
            }
        }
        cout << a.top() << " "; 
    }
    return 0；
}

请不要直接复制粘贴哦（

另外还看到了桶排序的做法，本来以为会超时，是我想太多了（）