【CF1394C】Boboniu and String 题解

题目大意

  给定 $n$ 个由 N 和 B 组成的字符串 $s_1,\cdots,s_n$，一个字符串可以做如下操作：增加或删去一个 B 我没有骂人、增加或删去一个 N、增加或删去一个 NB、增加或删去一个 BN。定义两个字符串的距离为：对一个字符串做最少多少次操作，可以使两个字符串的 N、B 数量分别相等。
  现给定 $s_1,\cdots,s_n$，求一个也由 N、B 构成的字符串 $t$，使得 $t$ 到 $s_1,\cdots,s_n$ 的最大距离最小。

  $n \leq 3\times 10^5,\ \ \sum|s_i| \leq 5 \times 10^5$
  3s

$$\\$$ $$\\$$ $$\\$$

题解

  我就一直在想，二分之后，怎么给这个奇怪的图形做扫描线求最大覆盖点呢？我就想啊想，想啊想……

  首先一个字符串与其 N、B 的顺序无关，只与 N、B 的数量有关，所以可以表示为平面上一个点 $(x_i,y_i)$。
  求最大值最小考虑二分，这个也很平凡。
  然后两个点的距离的定义也很显然：

$$dis((x,y),(x_i,y_i)) = \begin{cases} \max(|x-x_i|,|y-y_i|), & sgn(x-x_i)=sgn(y-y_i) \\ |x-x_i|+|y-y_i|, & sgn(x-x_i)\not=sgn(y-y_i) \end{cases}$$

  但二分之后每个点的形状却比较鬼畜

  这似乎不好做扫描线求最大覆盖点。。。

  于是换一种方法。
  假设当前二分到 $mid$，如果存在答案点 $(x,y)$ 到其他所有点距离不超过 $mid$，那么等价于满足如下条件：

$$\begin{aligned} \forall 1 \le i \le n,\ \ & x_i-mid \le x \le x_i+mid \\ &y_i-mid \le y \le y_i+mid \\ &|x-x_i+y_i-y|=|(x-y)-(x_i-y_i)| \le mid \end{aligned}$$

  其中前两个条件的作用很显然，否则无论 $sgn(x-x_i)$ 是否等于 $sgn(y-y_i)$，距离都会大于 $mid$。而第三个条件则用来限制 $sgn(x-x_i)\not=sgn(y-y_i)$ 的情况。（如果 $sgn(x-x_i)=sgn(y-y_i)$，那么满足了前两个条件会自然满足第三个条件；如果 $sgn(x-x_i)\not=sgn(y-y_i)$，那么 $|x-x_i+y_i-y|$ 就是两点的距离）

  于是这样就可以根据 $mid$ 来求出 $x,y,x-y$ 的合法区间，简单判断一下是否存在合法的 $x,y$ 即可。在二分时直接根据区间来判断，求答案时枚举一个 $x$。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;
typedef pair<int,int> pr;

const int maxn=3e5+5, maxlen=5e5+5;
const int inf=3e6+5;

int n,x[maxn],y[maxn];
char s[maxlen];

int ansb,ansn;
bool check(int mid,int ty)
{
	int xmin=0, xmax=inf, ymin=0, ymax=inf, dmin=-inf, dmax=inf;
	fo(i,1,n)
	{
		xmin=max(xmin,x[i]-mid);
		xmax=min(xmax,x[i]+mid);
		ymin=max(ymin,y[i]-mid);
		ymax=min(ymax,y[i]+mid);
		dmin=max(dmin,x[i]-y[i]-mid);
		dmax=min(dmax,x[i]-y[i]+mid);
	}
	if (xmin>xmax || ymin>ymax || dmin>dmax) return 0;
	ymin=max(ymin,xmin-dmax);
	ymax=min(ymax,xmax-dmin);
	if (ymin>ymax) return 0;
	if (ty)
	{
		fo(x,xmin,xmax)
		{
			int rymin=max(ymin,x-dmax), rymax=min(ymax,x-dmin);
			if (rymin<=rymax && (x>0 || rymax>0))
			{
				ansb=x, ansn=(x==0) ?rymax :rymin ;
				break;
			}
		}
	}
	return 1;
}

int main()
{
	scanf("%d",&n);
	fo(i,1,n)
	{
		scanf("%s",s+1);
		int len=strlen(s+1);
		fo(j,1,len) if (s[j]=='B') x[i]++; else y[i]++;
	}
	
	int l=0, r=2e6;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (check(mid,0)) r=mid-1; else l=mid+1;
	}
	
	printf("%d\n",++r);
	check(r,1);
	fo(i,1,ansb) putchar('B');
	fo(i,1,ansn) putchar('N');
	puts("");
}