此题可以三分套三分:
#include<iostream>
#include<utility>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
pair<int,int>b[(signed)3e5+9];
int bmax=0,nmax=0,nans;
int n;
int dist(pair<int,int>a,pair<int,int>b){
if(a==b)return 0;
if(a.first>b.first && a.second>b.second || a.first<b.first && a.second<b.second)return max(abs(a.first-b.first),abs(a.second-b.second));
return abs(a.first-b.first)+abs(b.second-a.second);
}
int solve(int bc){
int l=0,r=nmax;
int mx1,mx2;
while(l<=r){
int mid1=(2*l+r)/3;
int mid2=(2*r+l+2)/3;
mx1=0,mx2=0;
for(signed i=0;i<n;i++){
mx1=max(mx1,dist(make_pair(bc,mid1),b[i]));
mx2=max(mx2,dist(make_pair(bc,mid2),b[i]));
}
if(mx1>=mx2){
l=mid1+1;
}
else{
r=mid2-1;
}
}
nans=l;
return mx1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(signed i=0;i<n;i++){
string s;
cin>>s;
pair<int,int>bn;
for(int j:s){
if(j=='B')bn.first++;
else bn.second++;
}
if(bn.first>bmax)bmax=bn.first;
if(bn.second>nmax)nmax=bn.second;
b[i]=bn;
}
int l=0,r=bmax;
while(l<r){
int mid1=(2*l+r)/3;
int mid2=(2*r+l+2)/3;
if(solve(mid1)>=solve(mid2))l=mid1+1;
else r=mid2-1;
}
int a=solve(l);
cout<<a<<endl;
if(l==0 && nans==0)cout<<"BN";
else{
for(int i=0;i<l;i++){
cout<<'B';
}
for(int i=0;i<nans-1;i++)cout<<"N";
}
}
但是它为什么是一个单峰函数?