BZOJ1293: [SCOI2009]生日礼物【优先队列/堆】

dzy posted @ 2013年6月07日 00:10 in BZOJ with tags 优先队列 BZOJ , 2525 阅读

一直想做一道跟礼物有关的题、于是做了这道、

题意：长度为2^31的数轴上有n(<100w)个不同颜色的点，颜色种类<60，求一个长度最短的区间包含所有颜色的点。

思路好像很快就有了。记录每种颜色出现的第一个点和下一个点、把每种颜色的第一个点放进堆。这算一个初始答案。

之后每次把最左端的点从堆中删除、插入下一个这种颜色的点、直到删除的点没有后继了、那么答案也不能继续更新了（这不是废话？

那么就好了、我比较偷懒就用了priority_queue、、嘿嘿、、、（重载运算符真坑、、被坑了好久、、

BZOJ1293
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38	`#include<iostream>` `#include<cstdio>` `#include<cstring>` `#include<algorithm>` `#include<queue>` `using` `namespace` `std;` `const` `int` `inf=1000000009;` `int` `d[1000005],h[65],p[1000005],tot=0,L=inf,R=-1,An=inf;` `typedef` `struct` `gift{` `int` `x,y;` `gift(){}` `gift(int` `_x,int` `_y):x(_x),y(_y){}` `inline` `bool` `operator < (gift b)const{` `if(d[x]==d[b.x]){` `if(y==-1)` `return` `0;` `if(b.y==-1)` `return` `1;` `return` `d[y]>d[b.y];` `}return` `d[x]>d[b.x];` `}` `};` `priority_queue<gift>Q;` `inline` `void` `read(int` `&x){` `char` `ch;` `for(ch=getchar();ch<'0'\|\|ch>'9';ch=getchar());` `x=ch-'0';` `for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';` `}int` `main(){` `int` `n,k,t,x; read(n); read(k);` `memset(p,0xff,sizeof(p));` `while(!Q.empty()) Q.pop();` `for(int` `i=1;i<=k;i++){` `read(t); read(d[h[i]=tot++]);` `for(int` `x=h[i],j=2;j<=t;j++,x=p[x]) p[x]=tot++, read(d[p[x]]);` `Q.push(gift(h[i],p[h[i]])); L=min(L,d[h[i]]), R=max(R,d[h[i]]);` `}An=R-L;` `while(Q.top().y!=-1){` `gift u=Q.top(); Q.pop();` `if(d[u.y]>R) R=d[u.y]; Q.push(gift(u.y,p[u.y]));` `if(R-d[Q.top().x]<An) An=R-d[Q.top().x];` `}printf("%d\n",An);` `return` `0;` `}`

DZY 's BLOG