当前位置: 代码迷 >> 综合 >> codeforces721D Maxim and Array(贪心)
  详细解决方案

codeforces721D Maxim and Array(贪心)

热度:1   发布时间:2024-01-16 13:28:56.0

题意:

给出一系列数,要求可以进行k次操作,每次可以将数列中一个数+x或-x,求这些数的乘积的最小值。

要点:

这题就是贪心,如果负数是奇数个,就将当前数列中绝对值最小的数远离0,如果是偶数个,就靠近0。自己算算觉得还是挺靠谱的,感觉自己做还是不敢这么写。

#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 200000 + 5;
int n, k;
long long x;
typedef pair<long long, int> Pair;
priority_queue<Pair, vector<Pair>, greater<Pair>> q;int main()
{int p = 1,v,pos=1,s,g;long long a[maxn];scanf("%d%d%I64d", &n, &k, &x);for (int i = 1; i <= n; i++){scanf("%I64d", &a[i]);if (a[i] < 0) p ^= 1;//记录负数的个数,p为1为偶数,0为负数q.push(make_pair(abs(a[i]), i));}while (k){v = 1;pos = q.top().second; q.pop();if (p)//负数偶数个{v = -1;s = a[pos] < 0;}if (a[pos] < 0) a[pos] -= x*v;else a[pos] += x*v;if (p){g = a[pos] < 0;if (s != g)p^=1;}q.push(make_pair(abs(a[pos]), pos));k--;}for (int i = 1; i <= n; i++)printf("%I64d ", a[i]);printf("\n");return 0;
}


  相关解决方案