1293: [SCOI2009]生日礼物

题解：

　　据说这道题乱搞随便就水过了

　　本蒟蒻想到了一个用堆的水法（还专门学了学queue）：

　　如果把每一种颜色的下一个位置都记录一下的话，一开始就把所有的颜色开头位置加入堆中，求一下ans

　　然后将最左边的颜色删掉换成下一个位置并加入堆然后更新答案

　　因为题目保证位置升序，所以如果问当前颜色的没有了下一个位置，那就退出

代码（有点丑，因为不会求堆底所以开了两个堆）：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long LL;

 int n,k;

 struct node

 {

     LL x;int next;

     node(){next=-;}

     friend bool operator <(node n1,node n2)

     {

         return n1.x>n2.x;

     }

 }a[];

 struct node1

 {

     LL x;

     friend bool operator <(node1 n1,node1 n2)

     {

         return n1.x<n2.x;

     }

 }b[];

 priority_queue<node> q;

 priority_queue<node1> v;

 void clean(){while(q.empty()!=true)q.pop();}

 int t[];

 int main()

 {

     clean();int id=;

     scanf("%d%d",&n,&k);LL x;

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

     {

         scanf("%d",&t[i]);

         for(int j=;j<=t[i];j++)

         {

             scanf("%lld",&x);

             a[++id].x=x;if(j!=t[i])a[id].next=id+;

             b[id].x=x;

         }

     }

     int w=;

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

     {

         if(i!=)w+=t[i-];

         q.push(a[w]);v.push(b[w]);

     }

     node1 n1=v.top();

     node n2=q.top();

     LL ans=n1.x-n2.x;

     while()

     {

         node no=q.top();

         if(no.next==-)break;

         q.pop();q.push(a[no.next]);v.push(b[no.next]);

         n1=v.top();n2=q.top();

         ans=min(ans,n1.x-n2.x);

     }

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

     return ;

 }

巴特西

bzoj1293: [SCOI2009]生日礼物(stl堆)

1293: [SCOI2009]生日礼物

最新文章

热门文章