题解：CF721D Maxim and Array

· · 题解

题目传送门：CF721D Maxim and Array

Solution：

题意不解释。

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

如果乘积是正数，可以思考出将绝对值最小的数加到与之相反符号的数，例如将 -2 加到 1，5 减到 -1，使乘积变为负数。

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

注意到，一个绝对值最小的数让他加上（减去） x，是可以让总乘积变得最大。

例如：

5 1 3
5 4 3 5 -1

我们明显选择将 -1 减 3，可以造成 3\times (5+4+3+5) 的贡献，明显最优。

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

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

Code:

#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;
}

完结撒花！