题目：UOJ#264、洛谷P2827、Vijos P2007。
题目大意：给你$n$条蚯蚓的初始长度，每秒把一条最长的蚯蚓（设长度为x）切成长度$\lfloor px\rfloor$和$x-\lfloor px\rfloor$的两条蚯蚓（p为满足$0<p<1$的有理数，$p=\frac{u}{v}$，u和v输入给出）（注意切完后长度为0也要保留），切完后所有蚯蚓（不包括当前切出的两条）长度增加$q$。一共切$m$秒。需要输出第$t$秒，第$2t$秒，第$3t$秒……第$\lfloor \frac{m}{t}\rfloor t$秒所切的蚯蚓的长度是多少，以及$m$秒后第$t$长，第$2t$长，第$3t$长……第$\lfloor\frac{n+m}{t}\rfloor t$长的蚯蚓的长度是多少。
解题思路：首先我们给蚯蚓从大到小排序。然后可以发现，每次切出来的蚯蚓中，长的那写按切的顺序形成非上升序列，短的那些也如此。那么我们维护3个单调队列即可（原始蚯蚓也算一个单调队列），每次找三个队列队首元素最大的那个，把这个蚯蚓切掉，然后分别插入两个单调队列中。最后也按照这样每次找出最大的，按要求把该输出的输出即可。由于最后有$n+m$只蚯蚓，所以这样的时间复杂度$O(n+m)$。
UOJ的Extra Test会卡你$p$的精度，要用long double。
C++ Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
int y[7200005],d[7200005],x[7200005],ly,ry,ld,rd,lx,rx,n,m,q,u,v,t,pl,bufpos;
long double p;
char buf[30000000];
inline void init(){
bufpos=0;
buf[fread(buf,1,30000000,stdin)]='\0';
}
inline int readint(){
int p=0;
for(;!isdigit(buf[bufpos]);bufpos++);
for(;isdigit(buf[bufpos]);bufpos++)
p=(p<<3)+(p<<1)+buf[bufpos]-'0';
return p;
}
bool com(int a,int b){return a>b;}
int main(){
init();
memset(y,129,sizeof y);
n=readint(),m=readint(),q=readint(),u=readint(),v=readint(),t=readint();
p=(long double)u/v;
for(int i=1;i<=n;++i)y[i]=readint();
sort(y+1,y+n+1,com);
ly=ld=lx=1;
ry=n;
rd=rx=pl=0;
memset(d,129,sizeof d);
memset(x,129,sizeof x);
for(int i=1;i<=m;++i){
int yb=y[ly]+pl,db=d[ld]+pl,xb=x[lx]+pl;
pl+=q;
if(db>xb){
if(db>yb){
if(i%t==0)printf("%d ",db);
int a=(int)(db*p);
int b=db-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ld;
}else{
if(i%t==0)printf("%d ",yb);
int a=(int)(yb*p);
int b=yb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ly;
}
}else{
if(xb>yb){
if(i%t==0)printf("%d ",xb);
int a=(int)(xb*p);
int b=xb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++lx;
}else{
if(i%t==0)printf("%d ",yb);
int a=(int)(yb*p);
int b=yb-a;
if(a<b)swap(a,b);
d[++rd]=a-pl;
x[++rx]=b-pl;
++ly;
}
}
}
printf("\n");
int ct=0;
while(ly<=ry||ld<=rd||lx<=rx){
++ct;
int yb=y[ly]+pl,db=d[ld]+pl,xb=x[lx]+pl;
if(db>xb){
if(db>yb){
if(ct%t==0)printf("%d ",db);
++ld;
}else{
if(ct%t==0)printf("%d ",yb);
++ly;
}
}else{
if(xb>yb){
if(ct%t==0)printf("%d ",xb);
++lx;
}else{
if(ct%t==0)printf("%d ",yb);
++ly;
}
}
}
printf("\n");
return 0;
}