题目大意：
给定n头奶牛 给定n头奶头所在位置和品种 品种只有G H两种
求一段区间的长度 要求区间内包含的品种满足各品种的数量相同
将一个品种的值设为1 另一个设为-1
假设 i<j 而 1~i的奶牛前缀和 与 1~j的奶牛前缀和 相等
说明 i+1~j 的奶牛总和为0 即两种奶牛的数量相同
#include <bits/stdc++.h> using namespace std; #define LL long long #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define inc(i,l,r) for(int i=l;i<=r;i++) #define dec(i,r,l) for(int i=r;i>=l;i--) #define gcd(i,j) __gcd(i,j); const int N=1e5+5; const int mod=1e9+7; const double eps=1e-8; int n; struct NODE { int x,t; }a[N]; bool cmp(NODE p,NODE q) { return p.x<q.x; } int last[N<<1]; int main() { while(~scanf("%lld",&n)) { inc(i,1,n) { scanf("%d",&a[i].x); char c; scanf(" %c",&c); if(c=='G') a[i].t=1; else a[i].t=-1; } sort(a+1,a+1+n,cmp); mem(last,0); last[N]=a[1].x; int sum=N, ans=0; inc(i,1,n) { sum+=a[i].t; int t=ans; if(last[sum]==0) last[sum]=a[i+1].x; else ans=max(ans,a[i].x-last[sum]); } inc(i,1,n) { int j=i; while(j<=n && a[j].t==a[i].t) j++; j--; ans=max(ans,a[j].x-a[i].x); i=j; } // 只包含一个品种的情况 printf("%d ",ans); } return 0; }