LUOGU P2564 [SCOI2009]生日礼物 (队列+模拟)

解题思路

　　还是比较好想的，用一个队列，然后把所有点放在一起排个序，依次入队。每次检查队头元素的种类是否为当前入队元素种类，是的话就一直\(pop\)，每次更新答案即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

const int MAXN = 1000005;

inline int rd(){

	int x=0;char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return x;

}

int n,k,ans=1e9,cnt,num;

int vis[MAXN];

struct Data{

	int col,t;

	friend bool operator<(const Data A,const Data B){

		return A.t<B.t;

	}

}data[MAXN],tmp;

queue<int> Q;

int main(){

	n=rd();k=rd();int x;

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

		x=rd();tmp.col=i;

		while(x--) {tmp.t=rd();data[++cnt]=tmp;}

	}

	sort(data+1,data+1+cnt);

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

		Q.push(i);

		if(!vis[data[i].col]) num++;vis[data[i].col]=i;

		while(Q.size()){

			x=Q.front();if(vis[data[x].col]!=x) Q.pop();

			else break;

		}

		if(num==k) ans=min(ans,data[i].t-data[x].t);

	}cout<<ans;

	return 0;

}

巴特西

LUOGU P2564 [SCOI2009]生日礼物 (队列+模拟)

解题思路

代码

最新文章

热门文章