P3029 [USACO11NOV] Cow Lineup S

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=50010;
struct Cow{int x;int id;bool operator<(const Cow& t) const{return x<t.x;}
} a[N];
map<int,int> mp;
int n;
int cnt[N];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;int k=0;for(int i=1;i<=n;i++){int t;cin>>a[i].x>>t;if(!mp.count(t)){mp[t]=++k;}a[i].id=mp[t];}sort(a+1,a+n+1);int l=1;int now=0;int ans=2e9;for(int r=1;r<=n;r++){if(cnt[a[r].id]==0){now++;}cnt[a[r].id]++;while(now==k){ans=min(ans,a[r].x-a[l].x);cnt[a[l].id]--;if(cnt[a[l].id]==0) now--;l++;}}cout<<ans<<endl;return 0;}