题目描述
思路
- x、id不大于1亿，数据量太大，使用离散化
- 将id离散化成一串从1开始连续的编号，使用map集合进行离散化
- 使用双指针维护一段区间，这段区间满足每个编号都包含
如何使用map集合进行离散化？
- 维护一个变量nums，从1开始，每个编号的牛第一次被遍历的时候将nums作为新的编号，nums++
- 使用map集合判断这个牛的编号是不是第一次遍历， key值表示原编号，value表示新的编号
- 用一个结构体存储牛的信息：位置和编号，按位置进行排序，并且进行离散化的时候，将编号进行更新
- 定义一个队列，队列中存储每头牛的信息，将新的牛从队尾插入，并且记录这头牛的编号是否是第一次入列，当每个编号的牛都入列了，当前区间满足条件，进行比较
- 当最后一头牛入列并且队头存储的牛的编号只有一种时，退出循环
代码实现
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int N = 50010;
map<int, int> a; // 将ID编号离散化成一串连续的编号
int c[N]; // 下标为编号，出现了多少次
int nums; // 牛的种类
int n;
struct node
{
int x, id;
}niu[N], q[N]; // niu表示每头牛的信息：位置和编号
// q表示队列，存储牛的信息
bool cmp(node a, node b)
{
return a.x < b.x;
}
int main()
{
cin >> n;
for(int i = 0;i < n;i ++)
{
int id;
cin >> niu[i].x >> id;
if(!a.count(id)) // 如果当前编号没有出现过，牛的种类加1
{
nums++;
a[id] = nums;
}
niu[i].id = a[id]; // 将编号更新成新的编号
}
sort(niu, niu + n, cmp); // 按位置进行排序
int hh = 0, tt = 0; // hh队头、tt队尾
int res = 0; // 表示当前队列中有多少不同编号的牛
q[tt] = {niu[0].x, niu[0].id}; // 先将第一头牛的信息加入到队列中
res++;
int ress = 0x3f3f3f3f; // 满足条件的区间长度（是牛的位置距离）
c[niu[0].id]++; // 记录每个编号出现的次数
while(hh <= tt)
{
while(c[q[hh].id] > 1) // 判断队头，如果队头在队列中重复了，那么将队头弹出，
// 并且减少队头编号的数量，保证队列中满足条件并且位置距离最短
{
c[q[hh].id]--;
hh++;
}
if(res == nums) // 当前队列满足条件，比较位置距离
{
ress = min(ress, q[tt].x - q[hh].x);
}
if(tt == n-1) break; // 如果最后一头牛已经入队了，并且队头没有牛可以弹出了，循环结束
// 将新的牛加入到队尾中，并且判断这个牛的编号是不是第一次出现
q[++tt] = {niu[tt].x, niu[tt].id};
if(c[niu[tt].id] == 0) res++;
c[niu[tt].id]++;
}
cout << ress << endl;
return 0;
}
