題目描述
本題中，我們将用符号
表示對c向下取整，例如：
。
蛐蛐國最近蚯蚓成災了！隔壁跳蚤國的跳蚤也拿蚯蚓們沒辦法，蛐蛐國王隻好去請神刀手來幫他們消滅蚯蚓。
蛐蛐國裡現在共有n隻蚯蚓（n為正整數)。每隻蚯蚓擁有長度，我們設第i隻蚯蚓的長度為
，并保證所有的長度都是非負整數（即:可能存在長度為0的蚯蚓）。
每一秒，神刀手會在所有的蚯蚓中，準确地找到最長的那一隻（如有多個則任選一個）将其切成兩半。神刀手切開蚯蚓的位置由常數p(是滿足0<p<1的有理數)決定，設這隻蚯蚓長度為x，神刀手會将其切成兩隻長度分别為!和
的蚯蚓。特殊地，如果這兩個數的其中一個等于0，則這個長度為0的蚯蚓也會被保留。此外，除了剛剛産生的兩隻新蚯蚓，其餘蚯蚓的長度都會增加q(是一個非負整常數)。
蛐蛐國王知道這樣不是長久之計，因為蚯蚓不僅會越來越多，還會越來越長。蛐蛐國王決定求助于一位有着洪荒之力的神秘人物，但是救兵還需要m秒才能到來......
(m為非負整數）
蛐蛐國王希望知道這m秒内的戰況。具體來說，他希望知道：
•m秒内，每一秒被切斷的蚯蚓被切斷前的長度（有m個數）
•m秒後，所有蚯蚓的長度（有n+m個數)。
蛐蛐國王當然知道怎麼做啦！但是他想考考你......
輸入輸出格式
輸入格式：
第一行包含六個整數n,m,q,u,v,t，其中：n,m,q的意義見【問題描述】；u,v,t均為正整數；你需要自己計算p=u/v(保證0<u<v)t是輸出參數，其含義将會在【輸出格式】中解釋。
第二行包含n個非負整數，為
，即初始時n隻蚯蚓的長度。
同一行中相鄰的兩個數之間，恰好用一個空格隔開。
保證
，
輸出格式：
第一行輸出
個整數，按時間順序，依次輸出第t秒，第2t秒，第3t秒……被切斷蚯蚓（在被切斷前）的長度。
第二行輸出
個整數，輸出m秒後蚯蚓的長度；需要按從大到小的順序，依次輸出排名第t，第2t，第3t……的長度。
同一行中相鄰的兩個數之間，恰好用一個空格隔開。即使某一行沒有任何數需要 輸出，你也應輸出一個空行。
請閱讀樣例來更好地了解這個格式。
輸入輸出樣例
輸入樣例#1：
3 7 1 1 3 1
3 3 2 輸出樣例#1：
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2 輸入樣例#2：
3 7 1 1 3 2
3 3 2 輸出樣例#2：
4 4 5
6 5 4 3 2 輸入樣例#3：
3 7 1 1 3 9
3 3 2 輸出樣例#3：
//空行
2 說明
【樣例解釋1】
在神刀手到來前：3隻蚯蚓的長度為3,3,2。
1秒後：一隻長度為3的蚯蚓被切成了兩隻長度分别為1和2的蚯蚓，其餘蚯蚓的長度增加了1。最終4隻蚯蚓的長度分别為(1,2),4,3。括号表示這個位置剛剛有一隻蚯蚓被切斷
2秒後：一隻長度為4的蚯蚓被切成了1和3。5隻蚯蚓的長度分别為：2,3,(1,3),4。
3秒後：一隻長度為4的蚯蚓被切斷。6隻蚯蚓的長度分别為：3,4,2,4,(1,3)。
4秒後：一隻長度為4的蚯蚓被切斷。7隻蚯蚓的長度分别為：4,(1,3),3,5,2,4。
5秒後：一隻長度為5的蚯蚓被切斷。8隻蚯蚓的長度分别為：5,2,4,4,(1,4),3,5。
6秒後：一隻長度為5的蚯蚓被切斷。9隻蚯蚓的長度分别為：（1,4),3,5,5,2,5,4,6。
7秒後：一隻長度為6的蚯蚓被切斷。10隻蚯蚓的長度分别為：2,5,4,6,6,3,6,5,(2,4)。是以，7秒内被切斷的蚯蚓的長度依次為3,4,4,4,5,5,6。7秒後，所有蚯蚓長度從大到小排序為6,6,6,5,5,4,4,3,2,2
【樣例解釋2】
這個資料中隻有t=2與上個資料不同。隻需在每行都改為每兩個數輸出一個數即可。
雖然第一行最後有一個6沒有被輸出，但是第二行仍然要重新從第二個數再開始輸出。
【樣例解釋3】
這個資料中隻有t=9與上個資料不同。
注意第一行沒有數要輸出，但也要輸出一個空行。
【資料範圍】
吐槽
為啥我這篇博文标題要特地寫UOJ？因為UOJ的Extra Test很喪病的卡double的精度，u/v要long double才過得去，官方資料用double就夠了。
這題被選做NOI2017練習賽T1，下午學習了一波，晚上被熱的七葷八素，中暑成了CCF的孩～子……拖了3h才在洛谷上AC了這道題
解題思路
感覺這篇博文講的挺好的
http://www.cnblogs.com/ljh2000-jump/p/6189057.html//代碼在BZOJ會被卡精度PE
證明單調性的方法是這題最有趣的地方，方法不唯一哦
源代碼
//BZOJ、cogs會爆，不知為什麼
#include<cmath>
#include<queue>
#include<cstdio>
#include<algorithm>
std::queue<long long> que[4];
int n,m,u,v,p,t;
int queue[100010]={0};
int main()
{
//freopen("earthworm.in","r",stdin);
//freopen("earthworm.out","w",stdout);
scanf("%d%d%d%d%d%d",&n,&m,&p,&u,&v,&t);
long double q=(long double)(u)/(long double)(v);
for(int i=1,a;i<=n;i++)
scanf("%d",&queue[i]);
std::sort(queue+1,queue+n+1);
for(int i=n;i>0;i--)
que[1].push(queue[i]);
long long base=0;
for(int i=1;i<=m;i++)
{
long long qie=-2147483650;
long long pos=0;
for(int j=1;j<=3;j++)
{
if(!que[j].empty()&&que[j].front()>qie)
{
qie=que[j].front();
pos=j;
}
}
que[pos].pop();
qie+=base;
if(i%t==0) printf("%lld ",qie);
long long q1=(int)((long double)qie*q),q2=qie-q1;
base+=p;
q1-=base;q2-=base;
que[2].push(q2),que[3].push(q1);
}
printf("\n");
for(int i=1,mx=n+m;i<=mx;i++)
{
long long qie=-2147483650;
int pos=0;
for(int j=1;j<=3;j++)
{
if(!que[j].empty()&&que[j].front()>qie)
{
qie=que[j].front();
pos=j;
}
}
que[pos].pop();
if(i%t==0) printf("%lld ",qie+base);
}
return 0;
} 能在BZOJac的代碼：
http://blog.csdn.net/qzh_1430586275/article/details/53413950