题解 P3029 【[USACO11NOV]牛的阵容Cow Lineup】

糪眾脦颰罷 · 2018-10-26 09:12:59 · 题解

STL大法好！

感谢机房大佬 @S_AKM 提供的思路——尺取

其实我们可以不用hash,用map存种类就行了。（虽然比较慢）

此外，大致思路与其他题解相同。

贴代码

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x;
    int p;
};
node s[70000];
int ans=2e9,sum,n,z,tail;
map<int,int>t;
map<int,bool>pan;
bool cmp(node a,node b){
    return a.x<b.x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i].x>>s[i].p;
        if(pan[s[i].p]==false){
            sum++;
            pan[s[i].p]=true;//预处理一波，记录奶牛的种类总数
        }
    }
    sort(s+1,s+n+1,cmp);
    tail=1;
    t[s[1].p]++;
    z=1;
    for(int i=1;i<=n;i++){//以下思路与其他题解类似，就是用tail尾指针和头指针i不断查找更新答案
        while(z<sum&&tail<n){
            tail++;
            t[s[tail].p]++;
            if(t[s[tail].p]==1)z++;
        }
        if(z==sum)ans=min(ans,s[tail].x-s[i].x);
        t[s[i].p]--;
        if(t[s[i].p]==0)z--;
    }
    cout<<ans;
    return 0;
}