首页 > 代码库 > 【堆】bzoj1293 [SCOI2009]生日礼物
【堆】bzoj1293 [SCOI2009]生日礼物
考虑poj3320尺取法的做法，与此题基本一样，但是此题的 位置 的范围到2^31 尺取法不可。
将每种珠子所在的位置排序。
每种珠子要维护一个指针，指到已经用到这个种类的哪个珠子。
所以尺取法用堆优化，每次从堆中取出最小的，相当于尺取法的头指针向后移动。
然后从每种珠子里向后取出一个位置（指针++）（已经排过序，是单调递增的），加进堆。
再从每种其他的珠子里 把 在 新加入的珠子位置之前的 位置全都加进堆。
更新答案。
直到某种类珠子已经全用完。
由于每个位置可能有很多珠子，插入堆时要用一个二元组。
1 #include<cstdio> 2 #include<vector> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 struct Point 7 { 8 int x,y; 9 Point(const int &a,const int &b)10 {11 x=a;12 y=b;13 }14 Point(){}15 };16 bool operator < (const Point &a,const Point &b){return a.x!=b.x ? a.x<b.x : a.y<b.y;}17 bool operator > (const Point &a,const Point &b){return a.x!=b.x ? a.x>b.x : a.y>b.y;}18 priority_queue<Point,vector<Point>,greater<Point> >Heap;19 vector<int>a[61];20 vector<int>::iterator p[61];21 int n,m,k,t,maxv,time[61],ans=2147483647;22 Point topv;23 int main()24 {25 scanf("%d%d",&n,&m);26 for(int i=1;i<=m;i++)27 {28 scanf("%d",&k);29 for(int j=1;j<=k;j++)30 {31 scanf("%d",&t);32 a[i].push_back(t);33 }34 sort(a[i].begin(),a[i].end());35 p[i]=a[i].begin();36 }37 for(int i=1;i<=m;i++)38 {39 maxv=max(maxv,*a[i].begin());40 Heap.push( Point( *a[i].begin() , i ) );41 p[i]++;42 time[i]++;43 }44 for(int i=1;i<=m;i++)45 for(;p[i]!=a[i].end()&&((*p[i])<=maxv);p[i]++)46 {47 time[i]++;48 Heap.push( Point( *p[i] , i ) );49 }50 while(1)51 {52 topv=Heap.top();53 int headv=topv.y;54 ans=min(ans,maxv-topv.x);55 Heap.pop();56 time[headv]--;57 if(!time[headv])58 {59 if(p[headv]==a[headv].end())60 break;61 Heap.push( Point( *p[headv] , headv ) );62 maxv=*p[headv];63 time[headv]++;64 for(int i=1;i<=m;i++)65 for(;p[i]!=a[i].end()&&((*p[i])<=maxv);p[i]++)66 {67 time[i]++;68 Heap.push( Point( *p[i] , i ) );69 }70 }71 }72 printf("%d\n",ans);73 return 0;74 }
【堆】bzoj1293 [SCOI2009]生日礼物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。