CF1920B Summation Game

Zinc-Acetate / 2024-01-25 / 原文

题目传送门

codeforces

洛谷

题面

Alice and Bob are playing a game. They have an array $a_1, a_2,\ldots,a_n$. The game consists of two steps:

First, Alice will remove at most $k$ elements from the array.
Second, Bob will multiply at most $x$ elements of the array by $-1$.

Alice wants to maximize the sum of elements of the array while Bob wants to minimize it. Find the sum of elements of the array after the game if both players play optimally.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains three integers $n$, $k$, and $x$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq x,k \leq n$) — the number of elements in the array, the limit on the number of elements of the array that Alice can remove, and the limit on the number of elements of the array that Bob can multiply $-1$ to.

The second line of each test case contains $n$ integers $a_1, a_2,\ldots, a_n$ ($1 \leq a_i \leq 1000$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the sum of elements of the array after the game if both players play optimally.

题目大意

爱丽丝和鲍勃正在玩一个游戏。他们有一个数组 $a_1, a_2,\ldots,a_n$ 。游戏包括两个步骤：

首先，爱丽丝将从数组中移除最多 $k$ 个元素。
第二步，鲍勃将数组中最多 $x$ 个元素乘以 $-1$ 。

爱丽丝希望最大化数组元素之和，而鲍勃希望最小化数组元素之和。如果双方都以最佳方式进行游戏，请找出游戏结束后数组元素的总和。

思路

鲍勃肯定会选择更大的数进行乘以 $-1$ 操作，所以爱丽丝要想最大化数组元素之和，肯定要选择更大的数进行移除，但并不是移除的数最多最后的数组元素之和会最大，所以考虑枚举爱丽丝移除的数的数量，最后取最大值即可。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve()
{
    int n, k, x;
    cin >> n >> k >> x;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a.begin(), a.end());   // 排序
    vector<int> b(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        b[i] = b[i - 1] + a[i]; // 记录前缀和
    }
    int ans = LLONG_MIN;    // 答案初始化为一个很小的数
    for (int i = n; i >= n - k; i--)    // 枚举爱丽丝移除的数的数量
    {
        ans = max(ans, b[i] - 2 * (b[i] - b[max(0LL, i - x)]));
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}