题解：CF721D Maxim and Array
TANG2011
·
·
题解
前言
拉拉家常(bushi。
当然是讲一下悲惨事迹。
一道绿题调了两个半小时，发动了博主4个人的人脉，最终下课前一分钟调出来。
不就两个半小时嘛 你笑个屁。
特别鸣谢
@eddie08012025
@austin0116
@prettycai666
@louis_lxy
思路
首先考虑到贪心。
那么贪心策略是什么呢？
假设 x 为所有数中最小的，会有以下几种情况：
- 当总和能变为负数，则变为负数，剩下的次数都用来使每个数的绝对值变得平均，且绝对值需要变大。
- 当 x 只能变为 0，就把 x 变为 0，不做其他操作（想也操作不了啊）。
- 当 x 只能是正数，就把 x 变到最小。
接着考虑怎么做。
问题就转化为了解决问题 $1$，那么要如何维护每次更新完的的最小值呢？
我们可以想到优先队列，堆，set 等等。
我这里用 set 来维护~~绝对不是不会写优先队列~~。
提醒：记得用 multiset，防止被 set 去重了。
不过好像同学的 set 也能过？数据太水了？
其实不是的，如果你用 set，要重载运算符（operator）。
# 代码
码风太烂了勿喷。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200005];
int cnt;
struct node{
int x,y;
inline bool operator < (const node &o) const{
if(abs(x)!=abs(o.x))return abs(x)<abs(o.x);
return y<o.y;
}
};
multiset<node>st;
main(){
int n,k,x;
cin>>n>>k>>x;
int mn=2e18,ii=1;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]<0)cnt++;
if(abs(a[i])<mn){
ii=i;
mn=abs(a[i]);
}
}
if(mn-k*x>0){
a[ii]-=k*x;
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}else if(mn-k*x==0){
a[ii]=0;
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}else{
if(cnt%2==0){
int c=a[ii];
while(mn>=0){
k--;
mn-=x;
if(c>=0)a[ii]-=x;
else a[ii]+=x;
}
}
for(int i=1;i<=n;i++){
st.insert({a[i],i});
}
for(int i=1;i<=k;i++){
node p=*st.begin();
st.erase(st.begin());
if(p.x<0)p.x-=x;
else p.x+=x;
st.insert(p);
}
for(node p:st){
a[p.y]=p.x;
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
}
return 0;
}
```
[AC 记录](https://codeforces.com/contest/721/submission/320650932)