CF1920B 题解

yyrwlj · 2024-01-14 13:49:39 · 题解

题意简述

给定一个正整数序列，爱丽丝先从中删除最多 k 个数，鲍勃再从中选出最多 x 个数乘上 -1。

爱丽丝想让数列的和最大，鲍勃想让数列的和最小。求出双方操作一次后的数列和。

思路

先看鲍勃的操作，因为鲍勃想让数列的和最小，又因为是正整数数列，所以肯定会优先将更大的数乘上 -1。

同理，爱丽丝删除时，也要优先删除更大的数。

但是我们并不知道爱丽丝删多少个数最优，从 0 到 k 枚举即可。

为了方便用 O(1) 的时间求出每次枚举的结果，要将排完序的数列做一个正前缀和和负前缀和。

Code

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
int a[N], s1[N], s2[N];
bool cmp(int x,int y)
{
    return x > y;
}
void work()
{
    int n, k, x;
    scanf("%d%d%d", &n, &k, &x);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1, cmp);
    for (int i=1;i<=n;i++)
    {
        s1[i] = s1[i - 1] + a[i];
        s2[i] = s2[i - 1] - a[i];
    }
    int ans = -2e9;
    for (int i=0;i<=k;i++)
    {
        int l = i + 1, r = min(i + x, n);
        int res = s2[r] - s2[l - 1];
        ans = max(ans, res + s1[n] - s1[r]);
    }
    printf("%d\n", ans);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}