题目描述

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

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

题目思路

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

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

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

代码