自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:11:48，当前版本为作者最后更新于2025-04-04 17:00:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

如果一个匹配的两个端点位置分别是 $x$ 和 $y$，他们会把整个圆周化为两个部分——假设一个部分为 $w_1$ 个白点和 $b_1$ 个黑点，另一个部分是 $w_2$ 个白点和 $b_2$ 个黑点。

则这条线最多和 $\min\{w_1,b_2\} + \min\{w_2,b_1\} = \min\{w_1+b_1,w_2+b_2\}$ 条线相交（注意到 $w_1+w_2=b_1+b_2=n$）也就是 $\text{dis}(x,y)-1$，其中 $\rm dis$ 是环上两点的距离。

我们先最大化 $\sum \text{dis} (b_i,w_i) -1$。

看看这个图：

如果求红色点之间的距离，我们可以将其中一个红色的点对称到其对径点处，即计算下方红点和橙点的距离（用 $n$ 减去他们）。

因此问题变为：环上给了若干个白点和黑点，将其配对，最小化距离（为什么要最小化而不是直接最大化？因为圆上的距离本质上是两种方案取最小值。而如果先取最小值再尝试最大化一些东西，会导致出很多问题。。）

如果是序列上做这件事情，显然每条边会被经过的次数为：其左边的黑点总数与白点总数差的绝对值。所以我们不难猜测，最终的结果是——先匹配某个黑点和白点，然后不断移动他们顺时针方向下第一个黑点和第一个白点。有了这个结构，我们已经可以证明这种算法取到的解就是答案。

显然至少有一条边不会被经过，所以我们考虑选一个位置出来断环成链。

假设把 $1$ 和 $n+n$ 断开，记录 $pre_i$ 为：$\le i$ 的黑点个数减去白点个位数。

那么假设我们实际上在 $(p,p+1)$ 处断开，则新的 $pre'_i=pre_i - pre_p$。

所以我们要最小化 $\sum_{i=1}^{n+n} |pre_i-pre_p|$。

选中位数就好了。复杂度 $O(n \log n)$，如果换成桶排可以做到 $O(n)$。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int MAXN=1e6+10;
int n,pre[MAXN];
string S;
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>S,S="&"+S;
	ffor(i,1,n+n) if(S[i]=='B') pre[i]++;
	else pre[(i+n-1)%(n+n)+1]--;	
	ffor(i,1,n+n) pre[i]+=pre[i-1];
	sort(pre+1,pre+n+n+1);
	int ans=(n-1)*n;
	ffor(i,1,n+n) ans-=abs(pre[i]-pre[n]);
	cout<<ans/2;
	return 0;
}