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 ;
}