洛谷 P2564 [SCOI2009]生日礼物 题解

题目：P2564 [SCOI2009]生日礼物

队列 - 单调队列 - 双指针

双倍经验：P3029 [USACO11NOV]牛的阵容Cow Lineup

这里讲一种双指针的做法

首先将牛输入后，按坐标升序排列
维护指针 $l=1,r=0$，再维护数组 $c[]$ 记录每种珠子出现的次数， $cnt$ 为区间中珠子的种类的总数

如果 $cnt<k$，将区间向右扩张++r，并更新 $c[],cnt$
接着，将区间左端没用的珠子弹掉：
若区间最左端的珠子的种类在区间中出现不止一次，那么这个珠子就是没用的
弹完之后记得更新 $c[],cnt$

这样弄完一遍后，如果 $cnt=k$，就更新答案

关键代码

int l=1,r=0,cnt=0;
while(l<=n && r<=n)
{++r;c[a[r].id]++;if(c[a[r].id]==1)++cnt; // 维护 c[]和 cntwhile(1){if(c[a[l].id]<=1)break;c[a[l].id]--;++l;}if(cnt==k)ans=min(ans,a[r].pos-a[l].pos);
}

完整代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=1000000+10,inf=0x3f3f3f3f;
int n,k,ans=inf;
int c[100];
struct node{int pos,id; // 该珠子的位置和种类
}a[Maxn];
inline bool cmp(node x,node y)
{return x.pos<y.pos;
}
inline int read()
{int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();return s*w;
}
int main()
{
// freopen("in.txt","r",stdin);n=read(),k=read();int tmp=0;for(int i=1;i<=k;++i){int cnt=read();while(cnt--){int pos=read();a[++tmp].pos=pos;a[tmp].id=i;}}sort(a+1,a+1+n,cmp);int l=1,r=0,cnt=0;while(l<=n && r<=n){++r;c[a[r].id]++;if(c[a[r].id]==1)++cnt;while(1){if(c[a[l].id]<=1)break;c[a[l].id]--;++l;}if(cnt==k)ans=min(ans,a[r].pos-a[l].pos); // 更新答案}printf("%d\n",ans);return 0;
}