住房和城乡建设部干部学院网站,北京网站开发联系电话,青岛建设集团有限公司,邹城网站建设zc273500题目描述 思路
x、id不大于1亿#xff0c;数据量太大#xff0c;使用离散化将id离散化成一串从1开始连续的编号#xff0c;使用map集合进行离散化使用双指针维护一段区间#xff0c;这段区间满足每个编号都包含
如何使用map集合进行离散化#xff1f;
维护一个变量nums…题目描述 思路
x、id不大于1亿数据量太大使用离散化将id离散化成一串从1开始连续的编号使用map集合进行离散化使用双指针维护一段区间这段区间满足每个编号都包含
如何使用map集合进行离散化
维护一个变量nums从1开始每个编号的牛第一次被遍历的时候将nums作为新的编号nums使用map集合判断这个牛的编号是不是第一次遍历 key值表示原编号value表示新的编号用一个结构体存储牛的信息位置和编号按位置进行排序并且进行离散化的时候将编号进行更新定义一个队列队列中存储每头牛的信息将新的牛从队尾插入并且记录这头牛的编号是否是第一次入列当每个编号的牛都入列了当前区间满足条件进行比较当最后一头牛入列并且队头存储的牛的编号只有一种时退出循环
代码实现
#include iostream
#include map
#include algorithmusing namespace std;const int N 50010;
mapint, 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;
}
