1.2 提高組 

1.2.1　蚯蚓

【例題講解】蚯蚓（earthworm）NOIP 2016 

本題中，我們將用符號(hào)c表示對(duì)c向下取整，例如：3.0=3.1=3.9=3。

“蛐蛐國(guó)”最近蚯蚓成災(zāi)了！“蛐蛐國(guó)王”只好去請(qǐng)“神刀手”來(lái)幫他們消滅蚯蚓。

蛐蛐國(guó)里現(xiàn)在共有n（n為正整數(shù)）只蚯蚓。每只蚯蚓都有一定的長(zhǎng)度，我們?cè)O(shè)第i只蚯蚓的長(zhǎng)度為a_i （ i=1,2,…,n），并保證所有蚯蚓的長(zhǎng)度都是非負(fù)整數(shù)（可能存在長(zhǎng)度為0的蚯蚓）。

每一秒，神刀手都會(huì)在所有的蚯蚓中準(zhǔn)確地找到最長(zhǎng)的那一只（如有多只則任選一只），然后將其切成兩半。神刀手切開(kāi)蚯蚓的位置由常數(shù)p（p是滿足0＜p＜1的有理數(shù)）決定，設(shè)這只蚯蚓長(zhǎng)度為x，神刀手會(huì)將其切成兩只長(zhǎng)度分別為 px 和x-px 的蚯蚓。特殊地，如果這兩個(gè)數(shù)的其中一個(gè)為0，則這只長(zhǎng)度為0的蚯蚓也會(huì)被保留。此外，除了剛剛產(chǎn)生的兩只新蚯蚓，其余蚯蚓的長(zhǎng)度都會(huì)增加q（q是一個(gè)非負(fù)整數(shù)）。 

蛐蛐國(guó)王知道這樣不是長(zhǎng)久之計(jì)，因?yàn)轵球静粌H會(huì)越來(lái)越多，還會(huì)越來(lái)越長(zhǎng)。蛐蛐國(guó)王決定求助一位有著“洪荒之力”的神秘人物，但是救兵還需要m（m為非負(fù)整數(shù)）秒才能到來(lái)……蛐蛐國(guó)王希望知道：

m秒內(nèi)，每一秒被切斷的蚯蚓被切斷前的長(zhǎng)度（有m個(gè)數(shù)）； 

m秒后，所有蚯蚓的長(zhǎng)度（有n+m個(gè)數(shù)）。

【輸入格式】

第1行包含6個(gè)整數(shù)n,m,q,u,v,t，其中：n、m、q的意義見(jiàn)例題講解；u、v、t均為正整數(shù)；你需要自己計(jì)算p=u/v（保證0＜u＜v）的值；t是輸出參數(shù)，其含義將會(huì)在輸出格式中解釋。

第2行包含n個(gè)非負(fù)整數(shù)，為 a₁,a₂,…,a_n，即初始時(shí)n只蚯蚓的長(zhǎng)度。

同一行中相鄰的兩個(gè)數(shù)之間用一個(gè)空格分隔。

保證1≤n≤105，0≤m≤7×106，0＜u＜v≤109，0≤q≤200，1≤t≤71，0≤a_i≤108。

【輸出格式】

第1行輸出m/t個(gè)整數(shù)，按時(shí)間順序，依次輸出第t秒、第2t秒、第3t秒……被切斷蚯蚓（在被切斷前）的長(zhǎng)度。

第2行輸出(n+m)/t個(gè)整數(shù)，輸出m秒后所有蚯蚓的長(zhǎng)度：需要按從大到小的順序，依次輸出第t秒、第2t秒、第3t秒……時(shí)蚯蚓的長(zhǎng)度。

同一行中相鄰的兩個(gè)數(shù)之間用一個(gè)空格分隔。即使某一行沒(méi)有任何數(shù)需要輸出，也應(yīng)輸出一行空行。

請(qǐng)閱讀輸入樣例來(lái)更好地理解這個(gè)格式。

【輸入樣例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

【樣例1說(shuō)明】

在神刀手到來(lái)前：3只蚯蚓的長(zhǎng)度為3、3、2，p為1/3。

1秒后：一只長(zhǎng)度為3的蚯蚓被切成了兩只長(zhǎng)度分別為1和2的蚯蚓，其余蚯蚓的長(zhǎng)度增加了1。最終4只蚯蚓的長(zhǎng)度分別為（1、2）、4、3。括號(hào)表示這個(gè)位置剛剛有一只蚯蚓被切斷。

2秒后：一只長(zhǎng)度為4的蚯蚓被切成了1和3。5只蚯蚓的長(zhǎng)度分別為2,3,（1、3）,4。

3秒后：一只長(zhǎng)度為4的蚯蚓被切斷。6只蚯蚓的長(zhǎng)度分別為3,4,2,4,（1、3）。

4秒后：一只長(zhǎng)度為4的蚯蚓被切斷。7只蚯蚓的長(zhǎng)度分別為4,（1、3）,3,5,2,4。

5秒后：一只長(zhǎng)度為5的蚯蚓被切斷。8只蚯蚓的長(zhǎng)度分別為5,2,4,4,（1、4）,3,5。

6秒后：一只長(zhǎng)度為5的蚯蚓被切斷。9只蚯蚓的長(zhǎng)度分別為（1、4）, 3,5,5,2,5,4,6。

7秒后：一只長(zhǎng)度為6的蚯蚓被切斷。10只蚯蚓的長(zhǎng)度分別為2,5,4,6,6,3,6,5,（2、4）。

所以，7秒內(nèi)被切斷的蚯蚓的長(zhǎng)度依次為3,4, 4,4,5,5,6。7秒后，所有蚯蚓長(zhǎng)度從大到小排序?yàn)?,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

【樣例 2說(shuō)明】

這個(gè)樣例中只有t=2與上個(gè)數(shù)據(jù)不同。只需在每行都改為每?jī)蓚€(gè)數(shù)輸出一個(gè)數(shù)即可。

雖然第1行最后有一個(gè)6沒(méi)有被輸出，但是第2行仍然要重新從第2個(gè)數(shù)再開(kāi)始輸出。

【輸入樣例3】

3 7 1 1 3 9

3 3 2

【輸出樣例3】

2

【樣例3說(shuō)明】

這個(gè)數(shù)據(jù)中只有t=9與上個(gè)數(shù)據(jù)不同。注意：第1行沒(méi)有數(shù)要輸出，但也要輸出一行空行。

【算法分析】

一種簡(jiǎn)單的方法是將每一只蚯蚓的長(zhǎng)度都放入一個(gè)優(yōu)先隊(duì)列（大根堆）中，每次從堆頂（隊(duì)首）取出最長(zhǎng)的那只蚯蚓切成兩段，再將新產(chǎn)生的兩只蚯蚓直接放回優(yōu)先隊(duì)列即可，因?yàn)閮?yōu)先隊(duì)列的特性之一是自動(dòng)排序。神刀手操作m次后，逐個(gè)輸出隊(duì)首（堆頂）的數(shù)即可。這種使用STL中的優(yōu)先隊(duì)列存儲(chǔ)所有的蚯蚓，模擬神刀手的操作過(guò)程可以處理大部分測(cè)試數(shù)據(jù)。

要想通過(guò)全部測(cè)試數(shù)據(jù)，需要對(duì)操作過(guò)程進(jìn)行優(yōu)化，即神刀手每次操作后，其余蚯蚓的增長(zhǎng)沒(méi)有必要實(shí)時(shí)更新，可以定義一個(gè)變量sum統(tǒng)計(jì)其余蚯蚓的總增長(zhǎng)量。操作過(guò)程中，如果切斷的蚯蚓入隊(duì)，給它減去sum減去q的長(zhǎng)度；如果隊(duì)首的蚯蚓出隊(duì)，給它加上sum的長(zhǎng)度后再處理即可。

參考代碼如下。

 1  //蚯蚓 —— 使用優(yōu)先隊(duì)列模擬可處理大部分?jǐn)?shù)據(jù)
 2  #include <bits/stdc++.h>
 3  using namespace std;
 4 
 5  int main()
 6  {
 7    priority_queue<int> earthworm;  //優(yōu)先隊(duì)列默認(rèn)由大到小排列蚯蚓長(zhǎng)度 
 8    int n,m,t,q,u,v,sum=0;          //sum用于保存累計(jì)增加的q值
 9    cin>>n>>m>>q>>u>>v>>t;
 10    double p=double(u)/v;
 11    for(int i=0,temp; i<n; ++i)
 12    {
 13      cin>>temp;
 14      earthworm.push(temp);         //入隊(duì)列 
 15    }
 16    for(int i=1; i<=m; i++)
 17    {
 18      int Big=earthworm.top()+sum;  //隊(duì)首為最大值，出隊(duì)時(shí)還原回真實(shí)值
 19      earthworm.pop();              //刪除隊(duì)首的蚯蚓 
 20      if(!(i%t))                    //輸出第i*t秒切的蚯蚓
 21        cout<<Big<<" ";
 22      int cut=floor(p*double(Big)); //用floor函數(shù)，以防因編譯器不同而出現(xiàn)誤差 
 23      earthworm.push(cut-sum-q);    //被切割的蚯蚓無(wú)須加q,所以先減去 
 24      earthworm.push(Big-cut-sum-q);
 25      sum+=q;                       //累計(jì)增長(zhǎng)量
 26    }
 27    cout<<'\n';
 28    for(int i=1; i<=n+m; ++i)
 29    {
 30      if(!(i%t))
 31        cout<<earthworm.top()+sum<<' ';
 32      earthworm.pop();              //逐個(gè)刪除隊(duì)首的蚯蚓
 33    }
 34    cout<<'\n';
 35    return 0;
 36  }

因?yàn)槊恳淮尾僮鞫家页鲎畲蟮囊粋€(gè)數(shù)，如果用排序的方法會(huì)超時(shí)，所以考慮采用3個(gè)由大到小排列的隊(duì)列來(lái)完成（使用STL里的優(yōu)先隊(duì)列會(huì)超時(shí)，需要自己編寫(xiě)代碼）。第1個(gè)隊(duì)列p[0]保存的是已經(jīng)由大到小排好序的n只蚯蚓的長(zhǎng)度，p[2]、p[3]分別保存每一次切割后的前半段和后半段長(zhǎng)度，每次取3個(gè)隊(duì)列中隊(duì)首最大的元素進(jìn)行切割后存入p[2]和p[3]中，請(qǐng)思考p[2]、p[3]需要由大到小排序嗎？

試根據(jù)以上分析，完成滿分代碼（指完成的代碼可通過(guò)全部測(cè)試數(shù)據(jù)）。