题解 | #追求女神#

c题题解

思路

思路：使用优先队列 --> 大根堆 ，因为它会动态更新， 所以我们每次把里面的最大值也就是队头给减去p就行了
但是 因为一次一次的减去p，总共需要减去k次，k很大 会超时。
所以我们对于每一个取出的最大值 让他减去cnt次p。
cnt：减去cnt次p 后，该最大值 被 第二大的值 反超

但这样也有局限性，若我们得到的每个cnt都为1，最后还是需要执行k次减去p的操作。
比如 n个数均相同，我们会发现 每个cnt都是1。

但是 最后竟然过了，所以这题的数据还是挺水的ba。。。
综上：Code如下。

Code

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long ll;

const int N=1e6+10;

priority_queue<ll,vector<ll> > heap; //大根堆
ll a[N];
ll n,k,p;

int main(){
    cin>>n>>k>>p;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        heap.push(x);
    }

    if(p!=0){
        while(k){
         auto t=heap.top();
          heap.pop();
          ll cnt=(t-heap.top())/p+1;  //最大的减去cnt次后 会不再是最大数（变得小于第二大） 
          t-=cnt*p;
          k-=cnt;
          heap.push(t);
        }
    }


    int t=0;
    while(heap.size()){
        auto x=heap.top();
        a[t++]=x;
        heap.pop();
    } 

    for(int i=t-1;i>=0;i--){
        if(i==t-1) cout<<a[i];
        else cout<<" "<<a[i];
    }
    puts("");

    return 0;
}