自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:35:05，当前版本为作者最后更新于2022-01-04 08:51:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个挺有意思的题。

注意到当目前的总和绝对值是 $t$，新加入的数在 $[-x,x]$ 中的时候我们能够得到的值只能在 $[-x-t,x-t] \cup [-x+t,x+t]$ 中且能取遍其中任意整数。这个值域是关于 $0$ 对称的。

因此无论谁是最后操作者都想要最终绝对值最大，只要按照自己的要求取正负就可以了。故我们知道最后一个人肯定会选择 $-x_k-t$ 或 $x_k+t$，而其对手希望让这个绝对值尽可能小。由于 $x_k$ 给定，因此只要让 $t$ 尽可能小。这样讨论下去我们就会发现最后一个人会一直选择将绝对值从 $t$ 变成 $t+x_i$，其对手会一直选择将绝对值从 $t$ 变成 $\max\{t-x_i,0\}$。因此我们只要照此模拟即可。时间复杂度 $O(n)$。

Code:

#include<cstdio>
#define rg register
#define ll long long
int n,k,x,t;ll r;
int main(){
	n=read(),t=k=read();for(rg int i=0;i<n;++i){
		x=read(),r+=((i&1)?-x:x);
	}if(r<0)r=-r;while(k--){
		x=read(),r=(k&1)?((r>x)?(r-x):0):(r+x);
	}return 0&printf("%lld\n",(t&1)?r:-r);
}