Solution1
考虑如果白牛不能变花牛
如何迅速统计区间牛的数目——利用前缀和统计，设每个牛的 (v=1) ，求 (sum_i=sum_{j=1}^iv_j)
那么如何迅速判断是否满足白牛数=花牛数——不妨设白牛的 (v=1) ，花牛的 (v=-1) ，那么区间 ((l,r)) 满足条件就是 (sum_r-sum_{l-1}=0)
此时开一个 (map) 统计 (pre_{sum_i}) ， (pre_i) 代表 (i) 这个值第一次出现的地方， (O(n)) 扫描取 (max{pos_i-pos{_{pre_{sum_i}}}})
现在取消限制，白牛可以变花牛
那么区间满足的条件就得发生变化： (sum_r-sum_{l-1}equiv 0pmod 2)
说人话就是花牛和白牛一一配对后，剩下的白牛需要为偶数，这样才能保证将刚好一半的白牛转化成花牛，满足条件
此时如何统计答案呢？我们不能用 (O(n^2)) 去枚举→_→
因为上面用是 (O(n)) 扫描，下面不能更劣，所以也考虑扫描。（这理由好迷，性感理解）
分类讨论一下对于不同的 (sum) 怎么统计答案
-
当 (sum_i<0) 时，需要找一个 (j) 满足 (sum_i-sum_jgeq0(j<i)) 。
显然可得 (sum_j=sum_i) 时最优，因为 (sum_i-sum_j>0) 意味着还剩下几只白牛，但再加几只花牛总比白牛变花牛优(ง •_•)ง然后用有限制时的 (map) 法
-
当 (sum_igeq 0) 时，奇偶还得分开想
(sum_i) 为偶数时， 前 (i) 只牛都可以取。当 (sum_i) 为奇数时，还需要将第一只牛舍去，因为第一只牛不管是 (pm 1) ， (sum_i-sum_1) 肯定为偶数，并且最优。
时间复杂度： (O(nlog n)) 排序 (+) (O(n)) 扫描
细节：1.因为我们的 (pos_i) 是从坐标轴的 (1) 开始的，所以求 (sum_i>0) 且为偶数的区间长度时答案应该是 (pos_i-pos_1) ，奇数同理。2.记得排序，输入不保证有序。
Code1
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct node{
int pos;
int v;
}cow[N];
int sum[N],ans;
int n;
char op[2];
map<int,int> pre;
inline bool cmp(node a,node y){
return a.pos<y.pos;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%s",&cow[i].pos,op);
if(op[0]=='W') cow[i].v=1;
else cow[i].v=-1;
}
sort(cow+1,cow+n+1,cmp);
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+cow[i].v;
if(!pre[sum[i]]&&sum[i]<0) pre[sum[i]]=i;
else if(sum[i]<0) ans=max(ans,cow[i].pos-cow[pre[sum[i]]].pos);
if(sum[i]%2==0&&sum[i]>=0) ans=max(ans,cow[i].pos-cow[1].pos);
else if(sum[i]>=0) ans=max(ans,cow[i].pos-cow[2].pos);
}
printf("%d
",ans);
return 0;
}
你以为真的结束了吗？
不瞎细心的人会发现我上面写的是Solution1，所以现在是Solution2
Solution2
受机房奆佬ql12345指点此题可以用二分
预处理和Solution1的一样
剩下的就是二分区间长度，然后 (O(n)) 扫描是否存在满足题目条件的区间长度。
时间复杂度： (O(nlog n))
Code2
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int sum[N],ans;
struct node{
int pos;
int v;
}cow[N];
char op[2];
inline bool cmp(node a,node y){
return a.pos<y.pos;
}
inline bool check(int x){
int r=0;
for(int l=1;l<=n;l++){
while(cow[r].pos-cow[l].pos<x&&r<n) r++;
if(cow[r].pos-cow[l].pos<x) break;
if(sum[r]-sum[l-1]>=0&&(sum[r]-sum[l-1])%2==0) return true;
}
return false;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%s",&cow[i].pos,op);
if(op[0]=='W') cow[i].v=1;
else cow[i].v=-1;
}
sort(cow+1,cow+n+1,cmp);
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+cow[i].v;
int l=0,r=1e9+1;
while(r-l>1){
int mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d
",l);
return 0;
}
真的结束了_