可以发现,x和id的值都非常大,我们不能通过开一个109109的数组来存储品种为id的牛是否在区间内,但是牛的总数N只有50000,也就是说最多只会出现50000只id不同的牛.所以我们可以对id进行一个离散化,可以节省大量的空间.

离散化后,我们又该如何计算答案呢? 首先发现牛的顺序起初是无序的,处理不便,所以先将牛按照x值从小到大排序一下. 如果我们枚举每一个区间的话,复杂度为𝑂(𝑁2**)O(N2),会超时,此处我们可以通过two-pointers来优化算法.**

起初指针i,j都指向1号牛,将j指针不停向右移动,直到所以种类的牛都出现在区间里.此时更新答案,然后将i指针右移,直到区间里不包含所有种类的牛了,就重新将j指针向右移.重复这个过程即可. 这个算法i,j指针均不会后退,所以复杂度为𝑂(𝑁)O(N).

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;

const int N = 50010;

int n, cnt, ans = INT_MAX;
struct Cow {
	int x, id;
	bool operator < (const Cow &w) const {
		return x < w.x;
	}
} cow[N];
map<int, bool> used;
map<int, int> sum;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> cow[i].x >> cow[i].id;
		if (!used[cow[i].id]) {
			++cnt;
			used[cow[i].id] = true;
		}
	}
	sort(cow + 1, cow + n + 1);
	int num = 1;
	sum[cow[1].id] = 1;
	for (int i = 1, j = 1; i <= n; i++) {
		while (num < cnt && j < n) {
			j++;
			sum[cow[j].id]++;
			if (sum[cow[j].id] == 1) num++;
		}
		if (num == cnt) ans = min(ans, cow[j].x - cow[i].x);
		sum[cow[i].id]--;
		if (sum[cow[i].id] == 0) num--;
	}
	cout << ans << endl;
	return 0;
} 

这道题是一个单调队列的裸题

其实说单调队列也不是很确切，因为并没有从队头弹出再插入的操作

可以近似的看成贪心算法

贪心思路

首先，我们先把第一个元素压入队列

然后，对于每一个要进入队列的元素，在进入后，我们进行如下操作

1.将该元素代表的种类出现次数+1

2.如果队尾元素代表的种类出现了一次以上，我们就可以把队尾的元素舍弃掉，重复此操作直到队尾元素只出现了一次

3.如果队列内出现的所有种类都出现过了，更新答案

我们对上述操作逐个进行分析：

操作1，不用多讲

操作2，为什么队尾出现一次以上就可以弹掉？举个例子

下面是一个序列：（设pos = i）

1,2,3,1,2

最优的选法肯定是选择[2,4]或[3,5]

也就是说，后面进来的数将会给结果带来可能的更小值，而留在队尾的元素相当于拖累了答案的更新

为什么每一个数不进行判断就压入队列？

原因是一样的，越后面进入的数，就更有可能带来更小的结果

操作3，这个操作可以保证答案的正确性，使得我们的操作2不会舍弃掉某些中间出现的更优的答案

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define mod 11380
const int N=50005;
using namespace std;
int n,m,k,s,t,b[N],c[N],ans,now;
struct node{
	int x,id;
	bool operator<(const node &k)const{
		return x<k.x;
	}
}a[N];
int main()
{
//	freopen("in.txt","r",stdin);
	cin>>n;
	for (int i=1;i<=n;++i){
		cin>>a[i].x>>a[i].id;
		b[i]=a[i].id;	
	} 
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	m=unique(b+1,b+1+n)-b-1;
	for (int i=1;i<=n;++i)
		a[i].id=lower_bound(b+1,b+1+m,a[i].id)-b;
	int l=1;
	ans=0x3f3f3f3f;
	for (int r=1;r<=n;++r){
		c[a[r].id]++;
		if (c[a[r].id]==1) ++now;
		while (now==m && l<r && c[a[l].id]!=1) {
			--c[a[l].id];
			++l;
		}
		if (now==m) ans=min(ans,a[r].x-a[l].x);
	}
	cout<<ans;
}