照例化简题意:
给定一个 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, 那么答案不一定正确, 毕竟正整数的误差还是蛮大的)
- View Code
实数域二分:
- while((r-l)>0.000000001)
- {
- double mid=(l+r)/2;
- if(check(mid)==0)
- l=mid;
- else
- r=mid;
} 只要精度不出锅应该都没问题
View Code
(完)
来源: http://www.bubuko.com/infodetail-3265931.html