题目传送门：CF721D Maxim and Array

Solution：

题意不解释。

要求乘积最小，那么可以先将乘积变为负数。

如果乘积是正数，可以思考出将绝对值最小的数加到与之相反符号的数，例如将

-2

加到

1

，

5

减到

-1

，使乘积变为负数。

我们接着考虑使乘积继续变小。

注意到，一个绝对值最小的数让他加上（减去）

x

，是可以让总乘积变得最大。

例如：

CPP

5 1 3
5 4 3 5 -1

我们明显选择将

-1

减

3

，可以造成

3\times (5+4+3+5)

的贡献，明显最优。

解决完思路问题，接下来就是代码了。

我建议使用优先队列来查找每次绝对值最小的数。

Code:

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200010];

struct node{
	int x,i;
	operator < (const node o) const{
		return abs(x)>abs(o.x);
	}
};

priority_queue<node> q;

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,k,x,sum=1,f=1;
	cin>>n>>k>>x;
	for(int i = 1;i <= n;i++) cin>>a[i],sum*=(a[i]>=0?1:-1),q.push({a[i],i});
	if(!k){
		for(int i = 1;i <= n;i++)cout<<a[i]<<' ';
		return 0;
	} 
	if(sum>0){
		node h=q.top();
		q.pop();
		int a=h.x,b=abs(a)/x+1;
		if(b>k) b=k;
		k-=b;
		if(a>=0) q.push({a-b*x,h.i});
		else q.push({a+b*x,h.i});
	}
	if(!k){
		while(!q.empty()) a[q.top().i]=q.top().x,q.pop();
		for(int i = 1;i <= n;i++)cout<<a[i]<<' ';
		return 0;
	} 
	while(k--){
		node h=q.top();
		q.pop();
		int a=h.x;
		if(a>=0) q.push({a+x,h.i});
		else q.push({a-x,h.i});
	}while(!q.empty()) a[q.top().i]=q.top().x,q.pop();
	for(int i = 1;i <= n;i++)cout<<a[i]<<' ';
	return 0;
}

题解：CF721D Maxim and Array

文章操作

题目传送门：CF721D Maxim and Array

Solution：

Code:

完结撒花！

相关推荐

评论

题解：CF721D Maxim and Array