前言

~~拉拉家常(bushi~~。

当然是讲一下悲惨事迹。

一道绿题调了两个半小时，发动了博主4个人的人脉，最终下课前一分钟调出来。

不就两个半小时嘛 ~~你笑个屁~~。

特别鸣谢

eddie08012025 austin0116 prettycai666 louis_lxy

思路

首先考虑到贪心。

那么贪心策略是什么呢？

假设

x

为所有数中最小的，会有以下几种情况：

当总和能变为负数，则变为负数，剩下的次数都用来使每个数的绝对值变得平均，且绝对值需要变大。
当 $x$ 只能变为 $0$ ，就把 $x$ 变为 $0$ ，不做其他操作（想也操作不了啊）。
当 $x$ 只能是正数，就把 $x$ 变到最小。

接着考虑怎么做。

2

和

3

很好想，就是找到最小值

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 记录

题解：CF721D Maxim and Array

文章操作

前言

特别鸣谢

思路

代码

相关推荐

评论

题解：CF721D Maxim and Array