BZOJ1293：[SCOI2009]生日礼物

浅谈队列：https://www.cnblogs.com/AKMer/p/10314965.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=1293

这里介绍一种尺取法。（此处的尺意味游标卡尺）

从左至右依次测量以当前点为右端点的区间“长度”，那么左端点呢？

能用尺取法做的题必然满足当右端点不断往右移的时候，左端点不会往左移。

所以我们每次就去\(check\)一下左端点是否能往右移，如果可以那就不断地去“卡紧”测量范围。

对于这个题，用队列表示卡尺范围，我们可以开一个全局的桶，存每个颜色的彩珠在卡尺范围内有多少颗。如果左端点的彩珠颜色相同的区间内不止一颗那么肯定可以把左端点往右边靠的。然后每次更新最小值即可。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e6+5;

int sum[65],list[maxn];

int n,head,tail,ans=1e9,cnt,id;

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct cow {

    int pos,id;

    bool operator<(const cow &a)const {

        return pos<a.pos;

    }

}c[maxn];

int main() {

    n=read(),cnt=read();

	for(int i=1;i<=cnt;i++) {

		int tot=read();

		for(int j=1;j<=tot;j++)

			c[++id].pos=read(),c[id].id=i;

	}

    sort(c+1,c+n+1);

    for(int i=1;i<=n;i++) {

        int id=c[i].id;

        if(!sum[id])cnt--;

        sum[id]++;list[tail++]=i;

        while(sum[c[list[head]].id]>1)sum[c[list[head]].id]--,head++;

        if(!cnt)ans=min(ans,c[list[tail-1]].pos-c[list[head]].pos);

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

BZOJ1293：[SCOI2009]生日礼物

最新文章

热门文章