前缀和+哈希表
重点:
1.将H存为1,G为-1.这样当数量相等时和为0;
2.前缀和算区间内的牛是否公平。
3.看牛数量是否等是用前缀和s[r]-s[i-1](第i头牛到第r头牛数量公平),但是算距离需是用r-i的距离。
因此哈希表中sum要存后一个点的x
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
PII p[N];
int s1[N],s2[N];
int n;
int main(){
cin>>n;
unordered_map<int,int> hash;
char str[2];
int x;
for(int i=1;i<=n;i++)
{
scanf("%d%s",&x,str);
if(*str == 'H') p[i] = {x,-1};
else p[i] = {x,1};
}
sort(p+1,p+1+n);
int res = 0,last,sum=0;
for(int i=1;i<=n;i++)
{
if(!hash.count(sum)) hash[sum] = p[i].first;
sum += p[i].second;
if(hash.count(sum)) res = max(res,p[i].first - hash[sum]);
if(i==1 || p[i].second != p[i-1].second) last = p[i].first;
res = max(res,p[i].first - last);
}
cout<<res;
return 0;
}