自动搬运

查看原文

来自洛谷，原作者为

	orpg 抬头，即是星海

搬运于2025-08-24 23:07:26，当前版本为作者最后更新于2024-12-24 20:24:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

思路

不难发现，其实 Bessie 是没有选择的空间的，她只能合并最中间的两个蛋糕，不然的话 Elsie 就可以把 Bessie 合成的蛋糕藏起来。

举个例子。

如果有以下的蛋糕 ：

$[80,40,50,10,70,20]$。

Bessie 如果不合成中间两个蛋糕而选择合成 $[40,50]$。

第一步后：$[80,90,10,70,20]$。

对于 Elsie 最优选择是把 $80$ 藏起来。

第二步后：$[90,10,70,20]$。

所以不管 Bessie 之后怎么合 Elsie 都可以轻松的取走 Bessie 之前合成的东西。

所以，实际上整个游戏实际上是 Elsie 的主动权。整个题目就被简化成求 Elsie 的最大值。

在这之前我们先看一下两个人各能取多少个蛋糕。观察可得 Bessie 会在一开始拿走两个蛋糕，随后跟 Elsie 一样，一次取一个（因为 Bessie 只能合成最中间的两个）。所以不难发现 Bessie 一次可以取 $\frac{N}{2}+1$ 个，而 Elsie 一次可以取 $\frac{N}{2}-1$ 个（题目保证 $N$ 为偶数）。

对于 Elsie 不难发现，其实它是在不停的取左边或者右边。我们把该数列首尾拼接，则 Elsie 可以取到的蛋糕就是一个滑动的区间。

由上面的推理，不难得出 Elsie 只能拿 $\frac{N}{2}-1$ 个，在这里也就是 2 个，又因为 Elsie 只能从两边开始拿，所以它能拿的区间就是上图中的三个区间，最大值就显而易见了。

代码实现

我们可以把输入的数组重新存在原数组后面（以达到连接首尾的效果），然后对该数组求一个前缀和，这样可以快速的求出 Elsie 的最大值。然后把总其与总数相减，就是 Bessie 的答案了。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
int t,n;
int a[maxn];
ll sum[maxn];
ll all=0;
ll ans=0; 
void init(){
	memset(sum,0,sizeof sum);
	ans=0;
	all=0;
}
int main(){
	cin>>t;
	while(t--){
		init();
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i],all+=a[i],a[i+n]=a[i];
		int bessie=(n/2)+1,elsie=(n/2)-1;
		for(int i=(n/2)+2;i<=(3*n/2)-1;i++) sum[i]=sum[i-1]+a[i];
		for(int i=n;i<=(3*n/2)-1;i++){
			ans=max(ans,sum[i]-sum[i-elsie]);
		}
		cout<<all-ans<<" "<<ans<<'\n';
	}
}