Codeforces 721D Maxim and Array

链接

传送门

题意

给出$n$个数,每次选择一个数字加或减$x$,要求进行$k$次操作之后所有数字的乘积最小,输出操作后的数字。

思路

分情况讨论。注意要使乘积的绝对值变大时,一定是增加绝对值最小的数字的绝对值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <vector>
#include <queue>
#define X first
#define Y second
using namespace std;
typedef long long LL;
typedef pair<LL, int> pli;
const int maxn = 200010;
LL a[maxn];
int idx[maxn];
priority_queue<pli, vector<pli>, greater<pli>> q;
int main() {
int n, k, x;
scanf("%d%d%d", &n, &k, &x);
int cnt = 0, cnt1 = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
if (a[i] != 0) {
if (a[i] < 0) {
++cnt1;
}
q.push(make_pair(abs(a[i]), i));
} else {
idx[cnt++] = i;
}
}
if (cnt > k) {
a[1] += LL(k) * x;
} else {
if (cnt1 % 2 == 0) {
if (cnt > 0) {
a[idx[cnt - 1]] = -x;
q.push(make_pair(x, idx[cnt - 1]));
--cnt, ++cnt1;
--k;
} else {
pli p = q.top();
q.pop();
if (p.X < LL(k) * x) {
k -= p.X / x + 1;
p.X -= LL(p.X / x + 1) * x;
a[p.Y] = a[p.Y] > 0 ? p.X : -p.X;
++cnt1;
} else {
p.X -= LL(k) * x;
a[p.Y] = a[p.Y] > 0 ? p.X : -p.X;
}
q.push(make_pair(abs(a[p.Y]), p.Y));
}
}
if (cnt1 & 1) {
k -= cnt;
for (int i = 0; i < cnt; ++i) {
a[idx[i]] = x;
q.push(make_pair(x, idx[i]));
}
while (k--) {
pli p = q.top();
q.pop();
if (a[p.Y] < 0) {
a[p.Y] -= x;
} else {
a[p.Y] += x;
}
q.push(make_pair(abs(a[p.Y]), p.Y));
}
}
}
for (int i = 1; i <= n; ++i) {
printf("%lld ", a[i]);
}
puts("");
return 0;
}

支付宝扫码领红包