题解 | #追求女神#

集合操作

https://ac.nowcoder.com/acm/contest/11173/C

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;
}
全部评论
啊这,数据太水了吧。。。
点赞 回复 分享
发布于 2021-05-23 15:58

相关推荐

不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
05-19 19:57
蚌埠学院 Python
2237:Gpa70不算高,建议只写排名,个人技能不在多而在精,缩到8条以内。项目留一个含金量高的,减少间距弄到一页,硕士简历也就一页,本科不要写很多
实习,投递多份简历没人回...
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务