【noip2016】【洛谷P2827】蚯蚓

时间:2023-01-01 19:27:39

这个题只知道可以用优先队列去做,但是不知道正解想法,看到题解后恍然大悟,详情请看代码中间

#include<algorithm>
#include
<iostream>
#include
<cstring>
#include
<cstdio>
#include
<cmath>
using namespace std;
int n,m,q,u,v,t,q1[8000010],q2[8000010],q3[8000010],h1,h2,h3,t1,t2,t3;
bool cmp(int a,int b)
{
return a>b;
}
inline
int pop(int ti)
{
int top1=-1,top2=-1,top3=-1;
if(h1<=t1)
top1
=q1[h1]+(ti-1)*q;//对于初始的蚯蚓,开始时间是1
if(h2<=t2)
top2
=q2[h2]+(ti-h2-1)*q;//最早的被切开的蚯蚓开始增长于第二秒……所以多减个一
if(h3<=t3)
top3
=q3[h3]+(ti-h3-1)*q;
int flag=1,re=top1;
if(top2>re)//取个最大值
flag=2,re=top2;
if(top3>re)
flag
=3,re=top3;
if(flag==1)
h1
++;
if(flag==2)
h2
++;
if(flag==3)
h3
++;
return re;
}
inline
void push(int x)
{
long long qwq=(long long)x*u;
int a1=qwq/v,a2=x-a1;
if(a1<a2)
swap(a1,a2);
q2[
++t2]=a1,q3[++t3]=a2;//第二个队列放较大的,第三个放较小的
}
/*因为早分解的一定开始较大,所以他们分解出来的蚯蚓也一定会较大
所以我们可以开三个队列,分别用于维护未分解的蚯蚓,分解后较大的蚯蚓和较小的蚯蚓
那么每次所取的值,也一定在三个队列之首中的一个
我们记录头指针尾指针,他们除了作为指针也可以用于判断时间(很好理解,除了第一个队列,其他都是按照加入队列的时间来作为指针的)
这样我们先都分解一遍,然后再从剩下两个队列里面弹就行了(越靠近队首的越大)
*/
int main()
{
scanf(
"%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=1;i<=n;i++)
scanf(
"%d",&q1[i]);
sort(q1
+1,q1+1+n,cmp);
h1
=1,t1=n,h2=h3=1;
for(int i=1;i<=m;i++)
{
int qaq=pop(i);
if(i-i/t*t==0)//判断一下时间是不是t的倍数
cout<<qaq<<' ';
push(qaq);
}
cout
<<'\n';
for(int i=1;i<=m+n;i++)
{
int qaq=pop(m+1);
if(i-i/t*t==0)//判断下大小是不是t的倍数
cout<<qaq<<' ';
}
cout
<<'\n';
}