首页 > 代码库 > CF #374 (Div. 2) D. 贪心，优先队列或set
CF #374 (Div. 2) D. 贪心，优先队列或set
1、CF #374 (Div. 2) D. Maxim and Array
2、总结：按绝对值最小贪心下去即可
3、题意：对n个数进行+x或-x的k次操作，要使操作之后的n个数乘积最小。
（1）优先队列
#include<bits/stdc++.h>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=200100,MAX=1000100;struct Num{ int i; LL val; //一开始用int，一直挖9 bool operator <(const Num &a1)const { return abs(val)>abs(a1.val); }}a[N];int main(){ int n,k,num1; LL x; while(~scanf("%d%d%lld",&n,&k,&x)) { priority_queue<Num>Q; num1=0; F(i,0,n){ scanf("%lld",&a[i].val); a[i].i=i; Q.push(a[i]); if(a[i].val<0)num1++; } Num ans; while(k--){ ans=Q.top();Q.pop(); if(num1%2) { if(ans.val==0){ ans.val+=x; }else if(ans.val>0){ ans.val+=x; }else { ans.val-=x; } }else { if(ans.val==0){ ans.val-=x; if(ans.val<0)num1++; }else if(ans.val>0){ ans.val-=x; if(ans.val<0)num1++; }else { ans.val+=x; if(ans.val>=0)num1--; } } a[ans.i]=ans; Q.push(ans); } printf("%lld",a[0].val); F(i,1,n)printf(" %lld",a[i].val); puts(""); } return 0;}
（2）set
#include<bits/stdc++.h>#define F(i,a,b) for (int i=a;i<b;i++)#define FF(i,a,b) for (int i=a;i<=b;i++)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define LL long longusing namespace std;const int N=200010,MAX=1000100;int main(){ int n,k,flag; LL x,a[N]; while(~scanf("%d%d%lld",&n,&k,&x)) { flag=0; set<pair<LL,int> >S; F(i,0,n){ scanf("%lld",&a[i]); if(a[i]<0)flag^=1; S.insert(make_pair(abs(a[i]),i)); } while(k--){ int pos=S.begin()->second;S.erase(S.begin()); if(flag){ if(a[pos]>=0)a[pos]+=x; else a[pos]-=x; }else { if(a[pos]>=0){ a[pos]-=x; if(a[pos]<0)flag^=1; } else { a[pos]+=x; if(a[pos]>=0)flag^=1; } } S.insert(make_pair(abs(a[pos]),pos)); } cout<<a[0]; F(i,1,n)printf(" %lld",a[i]); cout<<endl; } return 0;}
CF #374 (Div. 2) D. 贪心，优先队列或set
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。