B. Summation Game
给你 \(n\) 个数(均大于0),Alice先执行一次删除不超过 \(k\) 个数,Bob再执行一次把最多 \(x\) 个数变成相反数.
问最后数组的最大和是多少?
这题本来是想先让Alice删除 \(k\) 个数,但显然不太容易得到最优解,因为还有可能撤回Alice的删除操作,再加上Bob的操作.
那如果先让Bob操作 \(x\) 个数,再看这 \(x\) 个数中最大的是不是大于剩下的最大的数的二倍,是否可行?
比如Bob操作的最大的数a,剩下的最大的数是b,那么如果Alice把a删掉,得到的新的数组的和应该是原数组的和 \(s+a-2b\),那只需要看a和2b的大小关系就可以了.
然而这只对应一个数的情况,如果是多个数,就不奏效了.
如下:
8 5 3
2 3 3 3 5 5 9 9
正解应该删除两个9,然后Bob操作 3 5 5
按我们的算法,Bob先操作5 9 9,然后我们进行判断Alice是否要删除9,Alice不会进行删除操作,因为9<2*5
然而考虑每次操作两个数: (3+5)*2 < (9+9) ,因此得到错误答案.
所以其实际需要满足的大小关系是 \(\sum a \geq 2 * \sum b\) ,而不是仅考虑单个的数
Solution
正解 枚举Alice删除前i个数后,Bob删除前x个数
for(int tk=0;tk<=k;tk++){
ans = max(ans,sum[n - tk] - 2*(sum[n-tk] - sum[max(0ll,n-tk-x)]));
}