自动搬运

查看原文

来自洛谷，原作者为

	糪眾脦颰罷 这个家伙很帅，什么也没有留下

搬运于2025-08-24 21:44:33，当前版本为作者最后更新于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;
}