前言

早年一直拿堆過不了，結果發現要用隊列

---

正題

題目鏈接:https://www.luogu.com.cn/problem/P2827

---

題目大意

有$n$條蚯蚓，每次選取最長的一條，切成$?x?p?$和$x??x?p?$的兩段，然后其余蚯蚓變長$q$。

求每次切開蚯蚓的長度和最后所以蚯蚓的長度。

---

解題思路

先不考慮變長

和合并果子的思路很像，我們發現如果從大到小切切出來的也是從大到小的，所以我們開三個隊列，第一個隊列裝初始的蚯蚓，然后切出來的左邊裝到第二個隊列，右邊裝到第三個隊列，這樣每個隊列的長度也是單調的，之后每次取出三個隊頭里最長的來剪掉就好了。

考慮變長，初始的蚯蚓第$i$次長度為$x+i?q$，那么我們直接當做所有長度都是$x+i?q$的蚯蚓，然后將第$i$次加入的蚯蚓長度變為$x?i?q$即可。

時間復雜度$O(n+m)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=7e6+10; ll n,m,q,u,v,t,a[N],q1[N*2],q2[N*2],q3[N*2]; int main() {scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+1+n);memset(q1,-127,sizeof(q1));memset(q2,-127,sizeof(q2));memset(q3,-127,sizeof(q3));ll h1,h2,h3,t1,t2,t3;h1=h2=h3=1;t1=t2=t3=0;for(ll i=n;i>=1;i--)q1[++t1]=a[i];for(ll i=1;i<=m;i++){ll l,r,x;if(q1[h1]>=q2[h2]&&q1[h1]>=q3[h3])x=q1[h1++];else if(q2[h2]>=q1[h1]&&q2[h2]>=q3[h3])x=q2[h2++];else x=q3[h3++];x+=(i-1)*q;l=x*u/v;r=x-l;q2[++t2]=l-q*i;q3[++t3]=r-q*i;if(i%t==0) printf("%lld ",x);}printf("\n");for(ll i=1;i<=m+n;i++){ll x;if(q1[h1]>=q2[h2]&&q1[h1]>=q3[h3])x=q1[h1++];else if(q2[h2]>=q1[h1]&&q2[h2]>=q3[h3])x=q2[h2++];else x=q3[h3++];if(i%t==0)printf("%lld ",x+m*q);} }

---

附上遠古時期堆的代碼

$90ptscode$

#include<cstdio> #include<algorithm> #define N 100010 #define M 7000010 using namespace std; int n,a[N+M],num,m,q,t,addl,u,v; double p; void up(int x) {while(x>1&&a[x>>1]<a[x]){swap(a[x],a[x>>1]);x>>=1;} } void down(int x) {int y;while((x<<1)<=num&&a[x<<1]>a[x]||((x<<1)|1)<=num&&a[(x<<1)|1]>a[x]){y=x<<1;if(a[y]<a[y|1]&&((x<<1)|1)<=num) y|=1;swap(a[x],a[y]);x=y;} } int main() {scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);p=(double)u/v;for(int i=1;i<=n;i++){scanf("%d",&a[i]);num++;up(num);}int k=1;for (int i=1;i<=m;i++){int k1,k2;a[1]=a[1]+addl;k1=(double)a[1]*p;k2=a[1]-k1;if(k==t){printf("%d ",a[1]);k=0;}a[1]=k1-addl-q;down(1);a[++num]=k2-addl-q;k++;up(num);addl+=q;}k=1;printf("\n");while(num){if(k==t) printf("%d ",a[1]+addl),k=0;swap(a[1],a[num]);num--;k++;down(1);} }

總結

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

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