自动搬运

查看原文

来自洛谷，原作者为

	薇蒻一枚 被JC了？挺好

搬运于2025-08-24 21:39:07，当前版本为作者最后更新于2019-07-30 22:29:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

背景

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