题目链接:这里
题意:给你n个数,你可以操作k次,每次使得一个数增加x或者减小x,你要使得最后所有数的乘积最小,问你最后这个序列长什么样子。
解法:贪心,根据符号的不同,每次贪心的使得一个绝对值最小的数减去x或者加上x就好了,这个贪心比较显然。假设当前乘积为ANS,那么你改变a[i]的大小的话,那么对答案的影响为ANS/A[i]/*X。然后找到影响最大的就好了。
//CF 721D
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
long long a[maxn];
int n, k, x;
set <pair <long long , long long> > S;
int main(){
scanf("%d%d%d", &n, &k, &x);
int sign = 0;
for(int i = 1; i <= n; i++){
scanf("%lld", &a[i]);
if(a[i] < 0) sign ^= 1;
S.insert(make_pair(abs(a[i]), i));
}
for(int i = 1; i <= k; i++){
int pos = S.begin()->second;
S.erase(S.begin());
if(a[pos] < 0) sign ^= 1;
if(sign) a[pos] += x;
else a[pos] -= x;
if(a[pos] < 0) sign ^= 1;
S.insert(make_pair(abs(a[pos]), pos));
}
for(int i = 1; i <= n; i++){
printf("%lld ", a[i]);
}
printf("\n");
}