題意：

相當于維護一個集合，支持查詢最大值、刪除最大值、插入新的值。時間卡的賊緊！！！！！！！！！！我不記得我T了幾次了都

思路：

根據輸入輸出以及n、m的數據范圍可以知道，需要在每秒進行切割時找出當前最大值，這時發現枚舉和堆、單調隊列等查找/維護最大值的方法是超時的。這時就有三個隊列q1、q2和q3，如果q1開始時單調遞減，每次取出最大值，然后將這個蚯蚓分開，把其中大的一部分壓入q2，小的一部分壓入q3，顯然，此時q1、q2和q3都是單調遞減的（所以每次的取出操作就可以是：在q1、q2、q3的隊首取出最大的一個）。
這時你會產生一個新疑問：怎樣讓蚯蚓生長呢？
我們發現，暴力將每次每只蚯蚓的長度加上q是不現實的，所以定義一個del，用來表示蚯蚓增長的長度，del初始時為零，每過一秒加上一個q。然后我們可以這樣想：在每一秒初，最長的蚯蚓被切開；在這一秒過程中，其他蚯蚓增長了q；在這一秒末，最長的蚯蚓被切成兩半，分別壓入數組中：
為什么是一個加del和一個減del的操作呢？數學證明：如果第a秒（此時del=(a-1)q）初取出一個長為s的蚯蚓，那么它的實際長度是（s+(a-1)q）,它會被切成兩半s1和s2在第a+1末被放回去，s1、s2就是這兩條新蚯蚓的初始長度，而放回去的是s1-a×q和s2-a×q。如果在第b+1秒初s1-a×q被取了出來，這時它會加上b×q成為s1-a×q+b×q。而在第a秒末到第b+1秒初中間有b-a秒，s1的長度應該是初始長度s1加上增加的長度(b-a)q，即s1+(b-a)q=s1-a×q+b×q。說白了就是讓s1,s2把給他們吃的q吐出來。

AC代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 7e6+10; inline int read() {int x=0,f=1; char ch=getchar();while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }return x * f; } int n,m,q,u,v,t,del; int h=1,h1=1,h2=1,t1,t2; int s[N],c1[N],c2[N]; priority_queue<int> pq; bool cmp(int a,int b) {return a > b; } int main() {n = read(), m = read(), q = read(), u = read() ,v = read() ,t = read();double p = (double)u/(double)v;for(int i=1;i<=n;++i) s[i] = read();sort(s+1, s+1+n, cmp);//第一個隊列用初始元素從小到大排序for(int i=1;i<=m;++i) {int tp,a1,a2;//tp為從三個隊列頭中選到的最大值if(h > n-1) c1[h1]>c2[h2] ? tp=c1[h1++] : tp=c2[h2++];//每只蚯蚓都被切過才比較else if(s[h]>=c1[h1] && s[h]>=c2[h2]) tp = s[h++]; else if(s[h]<=c1[h1] && c2[h2]<=c1[h1]) tp = c1[h1++];else tp = c2[h2++];tp += del; a1 = floor(p*(double)tp); a2 = tp - a1;//先加del再切模擬所有都長長了deldel += q; a1 -= del; a2 -= del;c1[++t1] = a1, c2[++t2] = a2;//c1,c2存切完后的if(i%t==0) printf("%d ",tp);}putchar('\n');//把結果弄在優先隊列里輸出for(int i=h;i<=n;++i) pq.push(s[i]);for(int i=h1;i<=t1;++i) pq.push(c1[i]);for(int i=h2;i<=t2;++i) pq.push(c2[i]);int i = 0;while(pq.size()) {++i; if(i%t==0) printf("%d ",pq.top()+del); pq.pop();}return 0; }

總結

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

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