首页 > 代码库 > CodeForces 721D Maxim and Array
CodeForces 721D Maxim and Array
贪心，优先队列。
先看一下输入的数组乘积是正的还是负的。
①如果是负的，也就是接下来的操作肯定是让正的加大，负的减小。每次寻找一个绝对值最小的数操作就可以了。
②如果是正的，也是考虑绝对值，先操作绝对值最小的那个数，直到那个数字的符号发生变化就停止操作，接下来就是第①步。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}LL ABS(LL a){ if(a>0) return a; return -a;}const int maxn=400010;int n,k; LL x;struct X{ LL x,y;int p; bool operator < (const X &a) const { return y>a.y; }}s[maxn];bool cmp2(X a,X b){ return a.y<b.y;}priority_queue<X>q;int cnt;LL ans[maxn];int main(){ scanf("%d%d%lld",&n,&k,&x); for(int i=1;i<=n;i++) { scanf("%lld",&s[i].x), s[i].p=i; s[i].y=ABS(s[i].x); if(s[i].x<0) cnt++; } if(cnt%2==0) { sort(s+1,s+1+n,cmp2); if(s[1].x<0) { while(k&&s[1].x<=0) { s[1].x+=x; k--; s[1].y=ABS(s[1].x); } } else { while(k&&s[1].x>=0) { s[1].x-=x; k--; s[1].y=ABS(s[1].x); } } for(int i=1;i<=n;i++) q.push(s[i]); while(k) { X h=q.top(); q.pop(); if(h.x>=0) h.x+=x; else h.x-=x; h.y=ABS(h.x); q.push(h); k--; } while(!q.empty()) { ans[q.top().p]=q.top().x; q.pop(); } } else { for(int i=1;i<=n;i++) q.push(s[i]); while(k) { X h=q.top(); q.pop(); if(h.x>=0) h.x+=x; else h.x-=x; h.y=ABS(h.x); q.push(h); k--; } while(!q.empty()) { ans[q.top().p]=q.top().x; q.pop(); } } for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl; return 0;}
CodeForces 721D Maxim and Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。