自动搬运

查看原文

来自洛谷，原作者为

	ycy1124 ENTJ-A | 有事私。| 清关了，私信基本也不会回关（除非满足条件），但可以支持小号回关 | 出去玩去了。不在线。微信可能上。

搬运于2025-08-24 22:03:05，当前版本为作者最后更新于2025-08-19 16:55:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

有一个长度为 $n$ 的 $v$ 序列。其中每个 $v_i$ 和 $v_{i+1}$ 之间有一个通道。特别的 $v_1$ 和 $v_n$ 之间有一个通道。现在有两个人 Alice 和 Bob 要在这个序列上移动且两个人都不能经过被其中任意一人经过的位置（起点也算）。由 Alice 先选择起点位置，然后 Bob 选择一个与 Alice 不同的位置作为起点。接下来两人按 Alice 先手，Bob 后手的顺序移动，每次两人可以选择移动到任意一个与自己经过的位置有通道相连的位置上面。Alice 希望自己经过的 $v$ 之和最大，而 Bob 希望这个值最小。试问 Alice 能取到的最大值为多少。

思路

不难发现 Alice 和 Bob 最终都会取到两端连续的区间且正好将整个 $v$ 序列覆盖。最终 Alice 取到的区间长度为 $\lceil \frac{n}{2}\rceil$，Bob 取到的区间长度为 $\lfloor \frac{n}{2}\rfloor$。两人的每次操作等价于将原本的区间向左或向右扩张一个位置。

首先肯定要破环为链，直接复制两倍。

然后考虑他们的最优策略。Alice 选择起点时我们显然没有什么好的策略，我们考虑 Bob 选什么起点能使 Alice 取到最小值。我们假设 Alice 的起点为 $i$，我们找到一个包含 $v_i$ 的 $v$ 值总和最小且长度为 $\lceil \frac{n}{2}\rceil$ 的区间。其左端点为 $l$，右端点为 $r$。我们发现，Bob 一定能找到一个起点使得 Alice 只能取到 $l\sim r$ 这个最小区间。为什么呢，我们考虑让 Bob 选择一个起点使得 Alice 的起点与 $l$ 的距离等于 Bob 的起点与 $l - 1$ 的距离且 Bob 的起点不在 $l$ 到 $r$ 的区间内。由于 Alice 的区间长度大于等于 Bob 的区间长度，所以 Bob 的起点距离 $r + 1$ 一定不会比 Alice 的起点距离 $r$ 更远。于是 Bob 只需要在 Alice 向 $l$ 扩展一步时向 $l - 1$ 扩展一步，Alice 向 $r$ 扩展一步时向 $r + 1$ 扩展一步就一定能使得 Alice 最终选择的区间为 $l\sim r$。不难证明这是 Bob 的最优策略。

因此我们只需要枚举每个 $i$ 找到包含这个点的最小区间，最后给这些区间的值取个 $\max$ 即可。

代码

这里选择的是单调队列搭配前缀和实现。其他很多数据结构也可以维护，但不建议使用线段树。

#include<bits/stdc++.h>//代码很丑，轻喷
#define int long long//_______,________.
#define N 3 * 500000 + 39
using namespace std;
int n, v[N], qzh[N], w[N], ans;
deque<int>q;
signed main()
{
	ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> v[i];
		v[n + i] = v[i];
		v[2 * n + i] = v[i];//为什么要复制三倍，因为作者写太丑了qwq
	}
	for(int i = 1; i <= 3 * n + 1; i ++)//前缀和
	{
		qzh[i] = qzh[i - 1] + v[i]; 
	}
	for(int i = 1; i + (n + 1) / 2 - 1 <= 3 * n + 1; i ++)//处理出以每个节点为左端点长度为ceil(n/2)的区间的和
	{
		w[i] = qzh[i + (n + 1) / 2 - 1] - qzh[i - 1];
	}
	for(int i = 1 - (n + 1) / 2 + 1 + n; i != n + 1; i ++) //单调队列，不会的可以去看滑动窗口（当然换成ST表等好理解的也可以）
	{
		while(!q.empty() && w[i] <= w[q.back()]) 
		{
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i = n + 1; i <= 2 * n; i ++)
	{
		while(!q.empty() && w[i] <= w[q.back()])
		{
			q.pop_back(); 
		}
		if(!q.empty() && q.front() + (n + 1) / 2 - 1 < i)
		{
			q.pop_front();
		}
		q.push_back(i);
		ans = max(ans, w[q.front()]);//虽然单调队列里是递减的，但是这里要取max
	}
	cout << ans;
	return 0;
}

AC 记录。