题解：P11973 [JOI Open 2020] 黑白点 / Monochrome Points

· · 题解

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;
}