想了想这个题好像不算单调队列,这个是维护一个不重复的区间的问题
很类似基础课的双指针算法第一题
这道题目区别在于一个位置可能有很多个气球
那么就开一个结构体记录 节点信息为(位置+气球种类编号) 然后对位置做排序
/*
*2021/12/6
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=1e6+10;
int n,k;
struct Node{
int ver,place;
bool operator <(const Node &t) const{
return place<t.place;
}
}p[N];
int cnt;
unordered_map<int,int> mp;
int cnt_mp;
int read()
{
int w=1;
char c=0;
int res=0;
while(c<'0'||c>'9'){
if(c=='-') w=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
res=res*10+c-'0';
c=getchar();
}
return res*w;
}
int main()
{
n=read(),k=read();
for(int i=1;i<=k;i++){
int t;
t=read();
for(int j=1;j<=t;j++){
int place;
place=read();
p[++cnt]={i,place};
}
}
sort(p+1,p+1+cnt);
/*for(int i=1;i<=cnt;i++){
printf("place is: %d ver is %d\n",p[i].place,p[i].ver);
}*/
int ans=0x3f3f3f3f;
int l=1;
for(int r=1;r<=cnt;r++){
if(!mp.count(p[r].ver)) cnt_mp++;
mp[p[r].ver]++;
while(mp[p[l].ver]>1){
mp[p[l].ver]--;
l++;
}
if(cnt_mp==k){
/*printf("now case is: ");
printf("left is %d right is %d\n",p[l].place,p[r].place);*/
ans=min(ans,p[r].place-p[l].place);
}
}
cout<<ans<<endl;
return 0;
}