小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。 小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西计算这个最短的长度么？彩带的长度即为彩带开始位置到结束位置的位置差。
Input
第一行包含两个整数N, K，分别表示彩珠的总数以及种类数。接下来K行，每行第一个数为Ti，表示第i种彩珠的数目。接下来按升序给出Ti个非负整数，为这Ti个彩珠分别出现的位置。
Output
应包含一行，为最短彩带长度。
Sample Input
6 3 1 5 2 1 7 3 1 3 8
Sample Output
3
Hint
有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据， N≤10000；
对于80%的数据， N≤800000；
对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。
思路：
很明显的尺取，开始终点移动走过一个点就把这个点上的所有珠宝都加入队列，当珠宝种类大于k时，起点移动，让珠宝出队列。不过要注意当一个点上的珠宝种类的数量正好为k是，其长度为1。从这道题也学到了pair和优先队列的结合使用，记一下。
ac代码：
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<string.h>
#include<set>
#define ll long long
#define PI acos(-1.0)
#define eps 1e-8
using namespace std;
typedef pair<int,int> pii;
pair<int,int> p1;
map<int,int> mp;
struct cmp{bool operator() (const pii p1,const pii p2){return p1.first > p2.first; /// first 小的先弹出}
};
int main()
{/*这里不用优先队列也可以，将信息存在一个结构体数组中，按照位置排一下序，然后扫一遍，扫到一个往后看看有没有位置和这个相同的，有就都加进来。或者用二维的vector，扫到一个点，把这一点对应的这一列都加入，求这一列的长度时，先定义一个变量接收size，否则在循环中写size()的话时间复杂度是O(n) *///priority_queue<pair<int,int>,vector<pii>,greater<pii> > que,q2;//也可以用上面的写法priority_queue<pair<int,int>,vector<pii>,cmp> que,q2;int len=0x3f3f3f3f;int n,k;scanf("%d%d",&n,&k);int num=0;for(int i=1;i<=k;i++){p1.second=i;int t; scanf("%d",&t);for(int j=0;j<t;j++){int wi;scanf("%d",&wi);p1.first=wi;que.push(p1); }} int st=que.top().first;int ed=que.top().first;while(!(que.empty()&&q2.empty())){while(num<k&&!que.empty()){p1=que.top();que.pop();ed=p1.first;if(mp[p1.second]==0)num++;mp[p1.second]++;q2.push(p1);while(!que.empty()&&que.top().first==p1.first){pair<int,int> p2;p2=que.top();que.pop();if(mp[p2.second]==0)num++;mp[p2.second]++;q2.push(p2);}}while(num==k&&!q2.empty()){int tt=ed-st;if(st==ed)tt=1;len=min(len,tt);p1=q2.top();q2.pop();mp[p1.second]--;if(mp[p1.second]==0)num--;while(!q2.empty()&&q2.top().first==p1.first){pair<int,int> p2;p2=q2.top();q2.pop();mp[p2.second]--;if(mp[p2.second]==0)num--;}st=q2.top().first;}if(num<k&&que.empty())break;}printf("%d\n",len);return 0;
}