題目傳送門（洛谷）

? ? ? ?題目大意：有n條蚯蚓，每次把最長的切成兩半，長度分別為?px?和x-?px?，其他的蚯蚓長度加q，重復m次，問某些時候切的蚯蚓的長度和最后的一些蚯蚓的長度。

? ? ? ?十分顯然的，這道題我們可以用堆輕易實現，用堆來維護最長的蚯蚓，拿出來切成兩半然后再塞回堆里面去。順手再輸出一下，這道題就ok了，于是我無腦的打出了以下代碼：

#include <cstdio> #include <cstring> #include <cmath> #define db doubleint n,m,q,u,v,tt; int t=0; struct node{int x,y;}; node dui[8000010]; void swap(node &x,node &y){node pp=x;x=y;y=pp;} int tot=0; void up(int x) {while(x>1&&dui[x].x+q*(tot-dui[x].y-1)>dui[x/2].x+q*(tot-dui[x/2].y-1)){swap(dui[x],dui[x/2]);x/=2;} } void down(int x) {if(x>t/2)return;int ans=x;if(dui[ans].x+q*(tot-dui[ans].y-1)<dui[x*2].x+q*(tot-dui[x*2].y-1))ans=x*2;if(x*2+1<=t&&dui[ans].x+q*(tot-dui[ans].y-1)<dui[x*2+1].x+q*(tot-dui[x*2+1].y-1))ans=x*2+1;if(ans!=x){swap(dui[x],dui[ans]);down(ans);} } void add(int x,int y) {dui[++t].x=x;dui[t].y=y;up(t); } node pop() {node re=dui[1];dui[1]=dui[t--];down(1);return re; }int main() {scanf("%d %d %d %d %d %d",&n,&m,&q,&u,&v,&tt);db p=(db)u/(db)v;for(int i=1;i<=n;i++){int x;scanf("%d",&x);add(x,0);}while(m--){node x=pop();tot++;if(tot%tt==0)printf("%d ",x.x+q*(tot-x.y-1));add((int)floor((db)(x.x+q*(tot-x.y-1))*p),tot);add((int)((db)(x.x+q*(tot-x.y-1))-floor((db)(x.x+q*(tot-x.y-1))*p)),tot);}printf("\n");int total=0;tot++;while(t){total++;node x=pop();if(total%tt==0)printf("%d ",x.x+q*(tot-x.y-1));} }

? ? ? ?一交上去，65分，頓時就懵逼了，翻翻討論發現這題貌似需要卡常，于是又加上了讀優以及一些硬核優化，于是。。變成了75分。。。

? ? ? ?傷感的提交記錄：

? ? ? ?然后，就只能想想其他做法了。（正文開始）

? ? ? ?想一想剛剛的堆的時間復雜度，O(mlogn)，看起來十分的優秀，仔細一想m是7*10^6，n是10^5，這個時間復雜度還是不怎么優的，于是，顯然的，正解一定是O(m)的！

? ? ? ?那么一想到每一次需要做到O(1)查詢最大值，毫無疑問一定是用優先隊列了（不是堆），于是考慮將一開始的蚯蚓排序，每次取第一個（也就是最大的），把它切了塞回隊列里面。

? ? ? ?相信聰明的你一定發現了問題——1、如何做到將其他的蚯蚓的長度+q ?； ?2、塞回隊列的時間是O(n)

? ? ? ?對于問題1，我們可以給每一只蚯蚓一個時間戳，記錄他是什么時候進入隊列的，那么每一次用 ? 原來的長度 + (現在的時間-進隊列的時間）*q ?便可以求出它現在的長度，具體實現方法可以參考上面的堆代碼。

? ? ? ?對于問題2，我們發現，不會優化。qaq

? ? ? ?于是發現把蚯蚓切成兩半后是不能塞回隊列的，那么，這個問題就轉化成了：如何處置這兩只蚯蚓？

? ? ? ?經過一番模擬后，發現每次被切出來的兩只蚯蚓，其實長度是單調不上升的，比如我在時刻1切了一只蚯蚓，切成x1和x2，時刻2又切了一只蚯蚓，切成y1和y2，同時，x1+q，x2+q，然后一做對比，此時的x1y1，并且x2y2。為啥？這里給出一種可能比較通俗易懂的

? ? ?證明：

? ? ? ?我們設在有兩只蚯蚓 f1,f2 分別在t1和t2時刻被切成兩半。（t1<t2）

? ? ? ?因為我們每次切的都是最長的蚯蚓，所以在t1時刻，f1f2

? ? ? ?我們把f1切成x1和x2后，在t1+1~t2這段時間，每次都是x1+q，x2+q，到了t2時刻的時候，x1變成了x1+(t2-t1-1)*q，x2變成了x2+(t2-t1-1)*q。

? ? ? ?為了簡化這個式子以及方便理解，我們設t2~t1+1這段時間一共有tc個單位時間，也就是tc=t2-t1-1，以及將t2時刻的x1、x2和f2寫為x1' , x2' , f2'

? ? ? ?于是式子變成了x1'=x1+tc*q，x2'=x2+tc*q

? ? ? ?以及f2'=f2+tc*q

? ? ? ?在t2時刻，我們將f2'切成了y1和y2，故y1=?p *?f2'?=?p * (f2+tc*q)? , y2=f2' -??p *?f2'?=(f2+tc*q)?-??p *?(f2+tc*q)?

? ? ? ?順便寫出x1和x2——x1=?p *?f1? , x2=f1?-??p * f1?

? ? ? ?將x1和x2帶入x1'和x2'中，得到x1'=?p *?f1?+tc*q，x2'=f1?-??p * f1?+tc*q

? ? ? ?于是我們先比較一下x1'和y1

? ? ? ?將x1'和y1整理一下就變成了

? ? ? ?x1'=?p *?f1?+tc*q=?p *?f1+tc*q?

? ? ? ?y1=?p * (f2+tc*q)?=?p * f2+p*tc*q)?（下面為了方便用一下LaTeX

? ? ? ?

? ? ? ?

? ? ? ?

? ? ? ?

? ? ? ?

? ? ? ?比較x2'和y2的過程類似，就不細講了（有興趣的話可以自己手推一下），由此"x1y1，并且x2y2"

?? ? 得證

? ? ? ?那么這道題的思路就很明顯了，開三個隊列，對于第一個隊列，存排好序的初始蚯蚓，第二個隊列存被切出來的長度為?px?的蚯蚓，第三個隊列存長度為x-?px?的蚯蚓，每次找出每條隊列中長度最大的蚯蚓進行比較，得到在所有蚯蚓中長度最大的那只，拿出來切開再塞回第二第三條隊列就好了。

? ? ? ?代碼如下：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std;int n,m,q,u,v,t,tot=0; double p; struct node{int x,y;int kk(){return x!=0?(x+(tot-y-1)*q):0;}//計算當前長度，因為我調用kk的時候都是在當前時間蚯蚓的長度還沒+q的時候，所以tot-y-1，還有如果x=0說明這個位置其實是沒有蚯蚓的，所以要返回0 }a[100010],b[7000010],c[7000010]; int sta=1,stb=1,stc=1,&eda=n,edb=0,edc=0; bool cmp(node x,node y){return x.x>y.x;} void work(node *f,int &st) {if(tot%t==0)printf("%d ",f[st].kk());//滿足要求就輸出b[++edb].x=(int)__builtin_floor((double)f[st].kk()*p);//__builtin_floor是向下取整，注意不能直接強行轉成intb[edb].y=tot;//記錄進隊列時間c[++edc].x=f[st].kk()-(int)__builtin_floor((double)f[st].kk()*p);c[edc].y=tot;st++; }int main() {scanf("%d %d %d %d %d %d",&n,&m,&q,&u,&v,&t);p=(double)u/(double)v;for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].y=tot;sort(a+1,a+n+1,cmp);while(m--){tot++;if(a[sta].kk()>=b[stb].kk()&&a[sta].kk()>=c[stc].kk())work(a,sta);//找出長度最長的蚯蚓else if(b[stb].kk()>=a[sta].kk()&&b[stb].kk()>=c[stc].kk())work(b,stb);else work(c,stc);}printf("\n");tot++;int total=0;while(sta<=eda||stb<=edb||stc<=edc){total++;//按長度依次彈出所有蚯蚓并輸出if(a[sta].kk()>=b[stb].kk()&&a[sta].kk()>=c[stc].kk())(total%t==0?printf("%d ",a[sta++].kk()):sta++);else if(b[stb].kk()>=a[sta].kk()&&b[stb].kk()>=c[stc].kk())(total%t==0?printf("%d ",b[stb++].kk()):stb++);else (total%t==0?printf("%d ",c[stc++].kk()):stc++);} }

? ? ? ?

總結

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

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