蛐蛐國最近蚯蚓成災了！

隔壁跳蚤國的跳蚤也拿蚯蚓們沒辦法，蛐蛐國王只好去請神刀手來幫他們消滅蚯蚓。

蛐蛐國里現在共有 n 只蚯蚓，第 i 只蚯蚓的長度為 ai ，所有蚯蚓的長度都是非負整數，即可能存在長度為0的蚯蚓。

每一秒，神刀手會在所有的蚯蚓中，準確地找到最長的那一只，將其切成兩段。

若有多只最長的，則任選一只。

神刀手切開蚯蚓的位置由有理數 p 決定。

一只長度為 x 的蚯蚓會被切成兩只長度分別為 ?px? 和 x??px? 的蚯蚓。

特殊地，如果這兩個數的其中一個等于0，則這個長度為0的蚯蚓也會被保留。

此外，除了剛剛產生的兩只新蚯蚓，其余蚯蚓的長度都會增加一個非負整數 q 。

蛐蛐國王知道這樣不是長久之計，因為蚯蚓不僅會越來越多，還會越來越長。

蛐蛐國王決定求助于一位有著洪荒之力的神秘人物，但是救兵還需要 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 個非負整數，為 a1,a2,…,an，即初始時 n 只蚯蚓的長度。

同一行中相鄰的兩個數之間，恰好用一個空格隔開。

輸出格式
第一行輸出 ?m/t? 個整數，按時間順序，依次輸出第 t 秒，第 2t 秒，第 3t 秒，……被切斷蚯蚓（在被切斷前）的長度。

第二行輸出 ?(n+m)/t? 個整數，輸出 m 秒后蚯蚓的長度；需要按從大到小的順序，依次輸出排名第 t，第 2t，第 3t，……的長度。

同一行中相鄰的兩個數之間，恰好用一個空格隔開。

即使某一行沒有任何數需要輸出，你也應輸出一個空行。

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

數據范圍
1≤n≤105,
0≤ai≤108,
0<p<1,
0≤q≤200,
0≤m≤7?106,
0<u<v≤109,
1≤t≤71
輸入樣例：
3 7 1 1 3 1
3 3 2
輸出樣例：
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
樣例解釋
樣例中，在神刀手到來前：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。

思路：
最直觀的思路是用一個優先隊列維護，但是m很大，這樣拿不了滿分。

考慮到，選中一個最長蚯蚓切的時候，除去切出來的這兩個蚯蚓其他蚯蚓都要加q。看起來當前的蚯蚓相對劣勢了。但是不然，當要切其他蚯蚓的時候也會經歷相同的情況，也就是說其實這些蚯蚓間是平等的！

放到切出來的蚯蚓長度上就是，當x1 ≥ x2時，x1切出來的蚯蚓對應x2切出來的蚯蚓也是單調遞減的。這樣可以用3個隊列維護3種值，且這三種值都是單調的，每次取最大的切就好了。

#include <cstdio> #include <cstring> #include <algorithm> #include <queue>using namespace std;typedef long long ll; queue<ll>q1,q2,q3; ll a[100005];int main() {int n,m,q,u,v,t;scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);for(int i = 1;i <= n;i++)scanf("%lld",&a[i]);sort(a + 1,a + 1 + n);for(int i = n;i >= 1;i--)q1.push(a[i]);ll delta = 0;for(int i = 1;i <= m;i++){ll mx = -1e9;int w = 0;if(q1.size() && mx < q1.front()){w = 1;mx = q1.front();}if(q2.size() && mx < q2.front()){w = 2;mx = q2.front();}if(q3.size() && mx < q3.front()){w = 3;mx = q3.front();}if(w == 1)q1.pop();if(w == 2)q2.pop();if(w == 3)q3.pop();mx = mx + delta;if(i % t == 0){printf("%lld ",mx);}ll x1 = mx * u / v - delta - q,x2 = mx - mx * u / v - delta - q;q2.push(x1);q3.push(x2);delta += q;}printf("\n");for(int i = 1;i <= m + n;i++){ll mx = -1e9;int w = 0;if(q1.size() && mx < q1.front()){w = 1;mx = q1.front();}if(q2.size() && mx < q2.front()){w = 2;mx = q2.front();}if(q3.size() && mx < q3.front()){w = 3;mx = q3.front();}if(w == 1)q1.pop();if(w == 2)q2.pop();if(w == 3)q3.pop();if(i % t == 0){printf("%lld ",mx + delta);}}return 0; }

總結

以上是生活随笔為你收集整理的ACWING133. 蚯蚓（栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。