方法思路

这个问题涉及Alice和Bob的最优策略：

1. Alice先移除最多d个数，她想要剩余数之和尽可能大
2. Bob接着将剩余数中最多m个数乘以-k，他想要剩余数之和尽可能小
3. 关键策略分析：
   • 将数组降序排序，最大的数在前面
   • Alice可以选择移除一些大数，防止Bob将它们变为负数
   • Bob会选择剩余数中最大的m个数乘以-k
   • 我们需要枚举Alice移除的数量(0到d)，计算每种情况下的最终和，找出最大值
4. 具体实现：
   • 对数组降序排序
   • 计算前缀和以便快速计算区间和
   • 枚举Alice移除的数量i (0≤i≤d)
   • 对于每种情况，计算Bob将剩余数中最大的min(m,n-i)个数乘以-k后的结果
   • 最终和 = 剩余所有数之和 - Bob操作的影响
   • 取所有情况中的最大值作为答案

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine().trim());
        
        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            
            st = new StringTokenizer(br.readLine());
            long[] nums = new long[n];
            for (int i = 0; i < n; i++) {
                nums[i] = Long.parseLong(st.nextToken());
            }

            // 使用快速排序代替Arrays.sort
            quickSort(nums, 0, n - 1);
            
            // 计算前缀和
            long[] prefixSum = new long[n];
            prefixSum[0] = nums[0];
            for (int i = 1; i < n; i++) {
                prefixSum[i] = prefixSum[i - 1] + nums[i];
            }

            long ans = Long.MIN_VALUE;
            
            // 特殊情况：Bob不能操作
            if (m == 0) {
                ans = prefixSum[n - 1];
            } else {
                // 枚举Alice移除的数量
                for (int i = 0; i <= d; i++) {
                    // 计算Alice移除i个数后的前缀和
                    long pre = (i > 0 ? prefixSum[i - 1] : 0);
                    
                    // 计算Bob能操作的最大下标（从i开始的m个数）
                    int j = Math.min(i + m - 1, n - 1);
                    
                    // 计算最终和
                    long sum = -k * (prefixSum[j] - pre) + (prefixSum[n - 1] - prefixSum[j]);
                    
                    ans = Math.max(ans, sum);
                }
            }
            bw.write(ans + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 快速排序（降序）
    private static void quickSort(long[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    
    private static int partition(long[] arr, int low, int high) {
        long pivot = arr[high];
        int i = low - 1;
        
        for (int j = low; j < high; j++) {
            if (arr[j] >= pivot) {  // 降序排序
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return i + 1;
    }
    
    private static void swap(long[] arr, int i, int j) {
        long temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Python

def solve():
    t = int(input())
    
    for _ in range(t):
        n, m, k, d = map(int, input().split())
        nums = list(map(int, input().split()))
        
        # 降序排序
        nums.sort(reverse=True)
        
        # 计算前缀和
        prefix_sum = [0] * n
        prefix_sum[0] = nums[0]
        for i in range(1, n):
            prefix_sum[i] = prefix_sum[i-1] + nums[i]
        
        ans = float('-inf')
        
        # 特殊情况：Bob不能操作
        if m == 0:
            ans = prefix_sum[n-1]
        else:
            # 枚举Alice移除的数量
            for i in range(min(d+1, n+1)):
                # 计算Alice移除i个数后的前缀和
                pre = prefix_sum[i-1] if i > 0 else 0
                
                # 计算Bob能操作的最大下标（从i开始的m个数）
                j = min(i + m - 1, n - 1)
                
                # 计算最终和
                sum_val = -k * (prefix_sum[j] - pre) + (prefix_sum[n-1] - prefix_sum[j])
                
                ans = max(ans, sum_val)
        
        print(ans)

if __name__ == "__main__":
    solve()

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m, k, d;
        cin >> n >> m >> k >> d;
        
        vector<long long> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        
        // 降序排序
        sort(nums.begin(), nums.end(), greater<long long>());
        
        // 计算前缀和
        vector<long long> prefixSum(n);
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i-1] + nums[i];
        }
        
        long long ans = LLONG_MIN;
        
        // 特殊情况：Bob不能操作
        if (m == 0) {
            ans = prefixSum[n-1];
        } else {
            // 枚举Alice移除的数量
            for (int i = 0; i <= min(d, n); i++) {
                // 计算Alice移除i个数后的前缀和
                long long pre = (i > 0) ? prefixSum[i-1] : 0;
                
                // 计算Bob能操作的最大下标（从i开始的m个数）
                int j = min(i + m - 1, n - 1);
                
                // 计算最终和
                long long sum = -k * (prefixSum[j] - pre) + (prefixSum[n-1] - prefixSum[j]);
                
                ans = max(ans, sum);
            }
        }
        
        cout << ans << endl;
    }
    
    return 0;
}