题目大意

给定一个序列 a1,a2,…,ana_1, a_2,\ldots, a_n，首先 A 先选择至多 kk 个数删除，然后 B 在剩下的数中选择至多 xx 个数乘上 −1-1，加上剩余的数后，A 想要和尽可能大，B 想要和尽可能小。若两者都通过最佳决策，求结果为多少。

解题思路

不难看出这是一道贪心题，数组中较大的数对结果的影响更大，因此我们可以进行从大到小的排序。但是不可以想当然让两者都选择当前序列中最大的数进行操作（样例中有反例）。

仔细分析样例后不难看出，A 选择的个数不大相同，但是 B 一定是尽可能选择完最大的，这样子最后的结果才会最小化。

到这里思路就很显然了，遍历枚举一遍 A 选择的个数，把每一个结果取一个 max⁡\max 即可。

你说循环求和会超时？用前缀和优化即可。

单次询问时间复杂度 O(nlog⁡n)O(n \log n)。

公式详推

定义 prei=a1+a2+a3+…+aipre_i = a_1 + a_2 + a_3 + \ldots + a_i，得出 A 删去的元素之和为：

preA=preipre_A = pre_{i}

得出 B 选择的元素之和为：

preB=prei+x−preipre_B = pre_{i + x} - pre_{i}

由此可以得出结果为

pren−2×preB−preA=pren−2×prei+x+preipre_n - 2 \times pre_B - pre_A = pre_n - 2\times pre_{i + x} + pre_i

需要注意的是，i+xi + x 可能会超过 nn，因此两者之间要取 min⁡\min。

AC Code

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
// Problem: B. Summation Game
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

// #define int long long

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2e5 + 9;
const int INF = 0x3f3f3f3f;

int a[N], pre[N], maxn;

void solve()
{
    maxn = -INF;		// 多测注意还原
    
    int n, k, x; cin >> n >> k >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    sort(a + 1, a + 1 + n, greater<>());	// 从大到小排序
    for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + a[i];	// 预处理前缀和数组
    
    for (int i = 0; i <= k; i ++) 		// i 指的是 Alice 要删除元素的个数
    {
        int res = 0;
        res = pre[n] - 2 * pre[min(i + x, n)] + pre[i];
        maxn = max(maxn, res);
    }
    cout << maxn << '\n';
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T --) solve();
    
    return 0;
}