给定$n$个$B,N$组成字符串$s$.每次操作可以增减$N,B,NB$。
$dis(s,t)$表示从$s\rightarrow t$所需要的操作次数。（只需要$N，B$的字符数量相同即可）。

求$min \sum \max dis(t,s_i)$

第一次做到关于线性规划的题。

坑定是二分答案。考虑经过至少$k$次之后是否达到所需的状态。

放在平面几何上就是有没有交点。观察其有6条边，即有6个约束情况

$\begin{cases} x_0-k\leq x \leq x_0+ k\\ y_0-k\leq y \leq y_0+ k\\ x_0-y_0-k\leq x -y\leq x_0-y_0+ k\\ \end{cases}$

然后暴力合并判断一下，然后枚举特殊点即可。

需要注意的是 $x-y$的最小值边界与$x，y$的最小值边界不相同
不能出现空串，就尽量拿$x-y$大的一边。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * f;
}

struct node
{
int l, r;
};
node p[N];

node c[3];
int n, ansx, ansy;
bool check(int v)
{
for (int t = 0; t < 3; t++)
c[t].l = -1e9, c[t].r = 1e9;
c[1].l = c[0].l = 0;
for (int i = 1; i <= n; i++)
{
int x = p[i].l, y = p[i].r;
c[0].l = max(c[0].l, x - v);
c[0].r = min(c[0].r, x + v);

    c[1].l = max(c[1].l, y - v);
    c[1].r = min(c[1].r, y + v);

    c[2].l = max(c[2].l, x - y - v);
    c[2].r = min(c[2].r, x - y + v);
}

for (int t = 0; t < 3; t++)
    if (c[t].r < c[t].l)
        return 0;
int l = c[0].l - c[1].r;
int r = c[0].r - c[1].l;

if (max(c[2].l, l) <= min(c[2].r, r))
{
    int k = max(c[2].l, l);
    int ls = max(c[0].l, c[1].l + k), rs = min(c[0].r, c[1].r + k);
    if (ls <= rs)
    {
        ansx = rs;
        ansy = rs - k;
    }
    return 1;
}
else
    return 0;

}
char s[N];
int main()
{
n = read();
for (int i = 1; i <= n; i++)
{
scanf(“%s”, s);
int len = strlen(s);
for (int j = 0; j < len; j++)
{
if (s[j] == ‘B’)
p[i].l++;
else
p[i].r++;
}
}
int l = 0, r = 1e6, ans = r;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
{
ans = mid;
r = mid - 1;
}
else
l = mid + 1;
}
cout << ans << endl;
cout << string(ansx, ‘B’) + string(ansy, ‘N’) << endl;
}