题目思路

对Bob来说，肯定是选择最大的m个数乘以-k，这样就可以让剩余数之和最小。

对于Alice来说，它可以选择去除0-d个元素。考虑去除x个元素，去除一个大的元素肯定比去除一个小的元素划算，因为大的那个乘以-k必然损失更大，所以Alice在去掉x个元素的情况下肯定是选择最大的x个元素去掉。

直接遍历去掉0-d个元素的所有情况，可以使用前缀和来维护Bob需要乘的值，时间复杂度$O(n)$

代码

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        while (T > 0) {
            T--;
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            int k = scanner.nextInt();
            int d = scanner.nextInt();
            List<Long> a = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                a.add(scanner.nextLong());
            }

            Collections.sort(a);
            Collections.reverse(a);

            for (int i = 1; i < a.size(); i++) {
                a.set(i, a.get(i) + a.get(i - 1));
            }

            long ans;
            if (m == 0) {
                ans = a.get(a.size() - 1);
            } else {
                ans = a.get(a.size() - 1) * (-k);
                for (int i = 0; i < d + 1; i++) {
                    long pre = (i > 0) ? a.get(i - 1) : 0;
                    int j = Math.min(i + m - 1, a.size() - 1);
                    ans = Math.max(ans, -k * (a.get(j) - pre) + a.get(a.size() - 1) - a.get(j));
                }
            }
            System.out.println(ans);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T > 0) {
        T--;
        int n, m, k, d;
        cin >> n >> m >> k >> d;
        vector<long long> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        sort(a.begin(), a.end(), greater<int>());

        for (int i = 1; i < a.size(); i++) {
            a[i] += a[i - 1];
        }

        long long ans;
        if (m == 0) {
            ans = a.back();
        } else {
            ans = a.back() * (-k);
            for (int i = 0; i < d + 1; i++) {
                long long pre = (i > 0) ? a[i - 1] : 0;
                int j = min(i + m - 1, (int)a.size() - 1);
                ans = max(ans, -k * (a[j] - pre) + a.back() - a[j]);
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Python

T = int(input())
while T > 0:
    T -= 1
    n, m, k, d = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[::-1]
    for i in range(1, len(a)):
        a[i] += a[i - 1]
    if m == 0:
        print(a[-1])
    else:
        ans = a[-1] * (-k)
        for i in range(0, d + 1):
            pre = a[i - 1] if i > 0 else 0
            j = min(i + m - 1, len(a) - 1)
            ans = max(ans, -k * (a[j] - pre) + a[-1] - a[j])
        print(ans)

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

这里有几个正整数，$a_1,...,a_n$，Alice 会先去掉其中最多 $d$个数

Bob 接下来会将剩余的数中最多$m$个数乘以 $-k$

Alice 想要剩余数之和尽可能大，Bob 想要剩余数之和尽可能小。

假设 Alice 和 Bob 都足够聪明，请问最后剩余数之和是多少。

输入描述

第一行一个正整数 $T$，接下来有 $T$ 组数据

每组数据$2$行

• 第一行4个数, $n,m,k,d(2\le n\le10^5)$$(0\le m,d\le n)(1\le k \le 10^4)$
• 第二行$n$个数，$a_1,a_2,...,a_n(1\le a_i\le 10^9)$

保证 $\sum{n}$ 不超过$10^5$

输出描述

输出$T$个整数，表示每组数据的剩余数之和

样例

输入

1
3 1 1 1
4 3 2

输出

1

说明

Alice不会去掉任何数
Bob会把4变为-4，此时剩余数为[-4,3,2]，和为1