首页 > 代码库 > [bzoj1293][SCOI2009]生日礼物
[bzoj1293][SCOI2009]生日礼物
给定n个k种礼物,没种礼物有一定的数量和坐标,你要选择最短的一段,使得这一段上有全部k种礼物。 n<=1000000
题解:很容易想到排序以后,两个坐标推一推 就没啦。
#include<iostream> #include<cstdio> #include<algorithm> #define MAXN 1000000 #define INF 2147483647 using namespace std; inline int read() { int x = 0 , f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar();} while(ch >= ‘0‘ && ch <= ‘9‘){x = x * 10 + ch - ‘0‘;ch = getchar();} return x * f; } struct N{ int k,x; }s[MAXN+5]; int n,k,tot=0,kind=0,ans=INF; int num[66]; bool cmp(N x,N y){return x.x<y.x;} void ins(int x){if(++num[x]==1)kind++;} void del(int x){if(--num[x]==0)kind--;} int main() { n=read();k=read(); for(int i=1;i<=k;i++) { int nn=read(); for(int j=1;j<=nn;j++) s[++tot].k=i,s[tot].x=read(); } sort(s+1,s+n+1,cmp); ins(s[1].k); for(int l=1,r=1;l<=n;del(s[l++].k)) { while(kind<k&&r<n) ins(s[++r].k); if(kind==k) ans=min(ans,s[min(r,n)].x-s[l].x); else break; } cout<<ans; return 0; }
[bzoj1293][SCOI2009]生日礼物
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。