照例化简题意：
给定一个01区间，可以把0改成1，问其中最长的01数量相等的区间长度。
额很容易想到前缀和，把w弄成1，h弄成-1，然后求前缀和，然后乱搞就行了。
但是一直不太会乱搞的我却直接想到了二分。
很容易很容易想到：答案有单调性，也就是：
答案肯定是单调不增的
怎么理解呢？
就是：一定存在一个区间长度，使得其-1不是最大，+1不存在，这就是我们要找的东西
而check的思路也就很明确了：
枚举左端点，然后根据二分出的mid（区间假定长度）来找到一个最长区间，然后判断其中白牛的数量是否为非负偶数：
如果白牛改的话，白-1，花+1，这样花牛的数量就比白牛多了2
若存在一个区间符合以上条件，就试着扩大区间（二分里l=mid），不符合就缩小区间，直到搜到答案。
需要注意的是：
如果搜到最后rx-lx达不到二分的区间长度，需要直接break掉，因为这里的答案不合法。
单次check的复杂度是O（n）的，因为lr端点都只遍历了一遍。
二分的复杂度是O（logn）
所以总复杂度就是O（n logn）
代码没什么大难度：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int n;
struct node
{
int x,co;
}a[maxn];
int sum[maxn];
int ans;
int f[maxn];
bool check(int x)
{
int r=0;
for(int l=1;l<=n;l++)
{
while(a[r].x-a[l].x<x&&r<n)r++;
if(a[r].x-a[l].x<x)break;
if((sum[r]-sum[l-1])%2==0&&sum[r]-sum[l-1]>=0)return 1;
}
return 0;
}
bool cmp(node a,node b)
{
return a.x<b.x;
}
int main()
{
//freopen("testdata.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
char f;
cin>>a[i].x>>f;
a[i].co=f=='W'? 1 : -1;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i].co;
int l=0,r=2147483647;
while(l<r-1)
{
int mid=l+r>>1;
if(check(mid)==0)
r=mid;
else
l=mid;
}
//while(check(l))l++;
printf("%d",l);
return 0;
}
下面谈谈二分答案：
一般，二分答案常用于：
- 寻找某东西的最大最小值/最小最大值
- 有单调性的答案寻找
而我遇到的二分差不多有三种（主要是check类型）：
- 跳石头类型（暴力判断）
- 本题（稍微转化下）
- 传送门（需要手推式子）
但是大体感觉都和跳石头差不多，找到条件，压掉一维O（n）的复杂度，使之变为log。
而二分很常用，很好用，要像想dp那样，经常想到。
下面介绍二分的板子（while内）
二分答案（正整数）：
while(l<r-1)
{
int mid=l+r>>1;
if(check(mid)==0)
r=mid;
else
l=mid;
}
while(check(l))l++;（因为输出左端点，而最后如果只更新了r，那么答案不一定正确，毕竟正整数的误差还是蛮大的）
实数域二分：
while((r-l)>0.000000001)
{
double mid=(l+r)/2;
if(check(mid)==0)
l=mid;
else
r=mid;
}只要精度不出锅应该都没问题
（完）