先按位置排序。
对于只有一种奶牛的情况，可以 \(O(n)\) 双指针解决。
对于有两种奶牛的情况，考虑做差来判重。
我们做一个前缀和，并在每一刻将差塞入一个数组（这里使用 map）。
时间复杂度 \(O(n\log n)\)。
Code：
#include<bits/stdc++.h>
using namespace std;
int n,num,ans,l=1,r=0,xo;
char ch;
struct cow {
int x;
int lx;
} a[100010];
bool cmp(cow a,cow b) {
return a.x<b.x;
}
map<int,int> pan;
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d %c",&a[i].x,&ch);
if(ch==‘G‘)
a[i].lx=1;
else
a[i].lx=-1;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) {
num+=a[i].lx;
if(pan[num])
ans=max(ans,a[i].x-a[pan[num]+1].x);
else
pan[num]=i;
}
r=1,xo=a[l].lx;
while(r<=n) {
if(a[r+1].lx==xo)
r++;
else {
r++,xo=a[r].lx;
while(a[l].lx!=xo)
l++;
}
ans=max(ans,a[r].x-a[l].x);
}
printf("%d",ans);
}
[USACO14OPEN]Fair Photography Bronze 题解
原文：https://www.cnblogs.com/lajiccf/p/13051179.html