1.2 提高組 

1.2.1　蚯蚓

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

本題中，我們將用符號c表示對c向下取整，例如：3.0=3.1=3.9=3。

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

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

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

蛐蛐國王知道這樣不是長久之計，因為蚯蚓不僅會越來越多，還會越來越長。蛐蛐國王決定求助一位有著“洪荒之力”的神秘人物，但是救兵還需要m（m為非負(fù)整數(shù)）秒才能到來……蛐蛐國王希望知道：

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

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

【輸入格式】

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

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

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

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

【輸出格式】

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

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

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

請閱讀輸入樣例來更好地理解這個格式。

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

在神刀手到來前：3只蚯蚓的長度為3、3、2，p為1/3。

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

【樣例 2說明】

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

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

【輸入樣例3】

3 7 1 1 3 9

3 3 2

【輸出樣例3】

2

【樣例3說明】

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

【算法分析】

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

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

參考代碼如下。

 1  //蚯蚓 —— 使用優(yōu)先隊列模擬可處理大部分?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)先隊列默認(rèn)由大到小排列蚯蚓長度 
 8    int n,m,t,q,u,v,sum=0;          //sum用于保存累計增加的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);         //入隊列 
 15    }
 16    for(int i=1; i<=m; i++)
 17    {
 18      int Big=earthworm.top()+sum;  //隊首為最大值，出隊時還原回真實值
 19      earthworm.pop();              //刪除隊首的蚯蚓 
 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);    //被切割的蚯蚓無須加q,所以先減去 
 24      earthworm.push(Big-cut-sum-q);
 25      sum+=q;                       //累計增長量
 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();              //逐個刪除隊首的蚯蚓
 33    }
 34    cout<<'\n';
 35    return 0;
 36  }

因為每一次操作都要找出最大的一個數(shù)，如果用排序的方法會超時，所以考慮采用3個由大到小排列的隊列來完成（使用STL里的優(yōu)先隊列會超時，需要自己編寫代碼）。第1個隊列p[0]保存的是已經(jīng)由大到小排好序的n只蚯蚓的長度，p[2]、p[3]分別保存每一次切割后的前半段和后半段長度，每次取3個隊列中隊首最大的元素進(jìn)行切割后存入p[2]和p[3]中，請思考p[2]、p[3]需要由大到小排序嗎？

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