求三分证明
查看原帖
求三分证明
484719
XSJProgrammer楼主2023/8/10 10:31

此题可以三分套三分:

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

但是它为什么是一个单峰函数?

2023/8/10 10:31
加载中...