P2564 生日礼物题解
背景
7月2*日既是某位兔子/狐狸/巫女/……小姐的生日,7月2*日又是本蒟蒻
的生日（洛谷送了我个橙名),樱(嘤)此写了一道叫做生日礼物的题。审题
1.通过审题我们不难想到一道类似的题目——逛画展。由此我们可以基本断定 这道题应该用单调队列。
2.两道题的唯一区别在于——一个结点上可以有多个彩球。
3.最后看数据规模——n已到达10e6的规模,因此暴力说不定能骗点分是不 可行的“不可以~”——zjh
思路
1.“既然两道题类似，那能不能继承P1638的思路呢”懒惰的jl想到。 其实两道题是可以互相转换的：我们可以定义一个结构体，结构体内储存 两个关键词——类型和位置。
2.以位置为关键字排序。
3..我们把同一位置的两个彩球拆开来看，即两个 类型不同，位置相同的小球，这样就可以继承P1638的思路了——因为在执行算法时，两者是没有区别的
代码(理论上AC了)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int n,k,t,len=0x3f3f3f3f;
int id[maxn],b;
struct node{
int pos;
int val;
}f[maxn];
bool cmp（n0de a,node b）
{
return a.pos<b.pos;
}
int main()
{
memset(id,-1,sizeof(id));
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
{
scanf("%d",&t);
for(int j=1;j<=t;j++)
{
scanf("%d",&f[++b].pos);
f[b].val=i;
}
}
sort(f+1,f+n+1,cmp);
int hd=1,cnt=0;
for(int i=1;i<=n;i++)
{
if(id[f[i].val]==-1) cnt++;
id[f[i].val]=f[i].pos;
while(hd<=i&&f[hd].pos!=id[f[hd].val]) hd++;
if(cnt==k&&f[i].pos-f[hd].pos<len) len=f[i].pos-f[hd].pos;
}
printf("%d",len）;
return o;
}
```cpp