第三题：1920 B. Summation Game

news/2025/2/12 10:51:44/

感觉自己的智慧不够，写不出来这题

我的思路是，先排序，然后Bob肯定是选择x个最大的数字乘以-1，Alice要是不移除元素，就会让Bob可以用更大的数字，移除元素会让总和变小，到底要不要移除元素，移除多少个元素，如果要移除元素肯定也是移除大的元素，把排序后的最后k+x个元素拿过来考虑，其他元素是不会影响最终答案的

移除0~k个元素，有k+1种选择，只要Alice做出决定，就可以决定Bob的决定，所以是不是可以直接枚举出答案，k,x在2e5范围内

数组下标不知道咋考虑，假设从n-k-x枚举到数组末尾，算了一下确实可以表示能被操作的所有元素

然后用一个类似于滑动窗口的思路来做这题嘛（明天再来试试）

不移除相当于在前面元素的基础上加上一些元素，Bob的操作是前面元素的基础上减去一些元素，所以其实这里的差距是两倍原来的元素

移除的话，差距是两倍Bob操作的元素再加上移除的元素，移除的话，Bob操作的元素会变小，所以就是一个贪心策略

是不是要用前缀和来表示

让最后面的几个元素的和最小就可以保证所有元素的总和最大，这就是Alice的最优策略

但是不知道怎么用代码实现

#include<bits/stdc++.h>using namespace std;const int N=2e5+10;
int a[N];
int s[N];void solve()
{int n,k,x;cin>>n>>k>>x;for(int i=1;i<=n;i++)	cin>>a[i];sort(a+1,a+1+n,greater<int>());for(int i=1;i<=n;i++)	s[i]=s[i-1]+a[i];int ans=-0x3f3f3f3f;for(int i=0;i<=k;i++)ans=max(ans,s[n]-s[min(i+x,n)]-(s[min(i+x,n)]-s[i]));cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);//cout<<0x3f3f3f3f<<endl;int t;cin>>t;while(t--)solve();return 0;
}