本文共 1863 字，大约阅读时间需要 6 分钟。
给定一个序列，每次可以选一个ai，ai+x或者ai-x。操作次数不超过k次。问结果序列之积最小是多少?
联想到和一定的序列在每一个元素最相近的时候积最小，所以用一个优先队列，每次取出绝对值最小的元素，正＋x，负－x就可以了。
虽然如此但是contest的时候还是wa了，因为有比较多的分类需要讨论。首先就是0怎么处理，如果有零，不能粗暴的决定变正还是负，要根据负数的个数的奇偶性判断。处理完0之后如果负数的个数是偶数个，仍然要处理。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define FORD(i,k,n) for(int i=n;i>=k;i--)#define FOR(i,k,n) for(int i=k;i<=n;i++)#define CLR(a,b) memset(a,b,sizeof(a));#define INF 0x3f3f3f3f#define LLINF 0x3f3f3f3f3f3f3f3f#define ll long long#define LL long long#define ull unsigned long long#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define ptb(b,a){int tmp=a;string s;do{s+=tmp%2+'0';tmp/=2;}while(tmp);reverse(s.begin(),s.end());cout<<"bin "<<<"="<< abs(rhs.v); }}b[maxn];priority_queue q;int n,k;ll x;ll a[maxn];int cntf,cntz;void read(){ FOR(i,0,n-1) { cin>>a[i]; b[i].idx=i; b[i].v=a[i]; if(a[i]<0) cntf++; else if(a[i]==0) cntz++; }}void solve(){ FOR(i,0,n-1) q.push(b[i]); int flg=0; while(k&&cntz) { k--; cntz--; node tmp=q.top(); q.pop(); if(cntf%2==1) { a[tmp.idx]+=x; tmp.v+=x; } else { a[tmp.idx]-=x; tmp.v-=x; cntf++; } q.push(tmp); } if(cntf%2==0) { node tmp=q.top(); q.pop(); if(tmp.v>0) { while(k&&tmp.v>=0) { k--; tmp.v-=x; a[tmp.idx]-=x; } } else { while(k&&tmp.v<=0) { k--; tmp.v+=x; a[tmp.idx]+=x; } } q.push(tmp); } while(k) { k--; node tmp=q.top(); q.pop(); if(tmp.v>0||(tmp.v==0&&flg==2)){ tmp.v+=x; a[tmp.idx]+=x; } else if(tmp.v<0||(tmp.v==0&&flg==1)) { tmp.v-=x; a[tmp.idx]-=x; } q.push(tmp); } FOR(i,0,n-1) { if(i!=n-1) cout< <<" "; else cout< < >n>>k>>x; read(); solve(); return 0;}
转载于:https://www.cnblogs.com/diang/p/5934014.html
