#185. [NOIP2016 提高组] 蚯蚓题解
#185. [NOIP2016 提高組] 蚯蚓題解
題目描述
本題中,我們將用符號 ?c?\lfloor c \rfloor?c? 表示對 ccc 向下取整,例如:?3.0?=?3.1?=?3.9?=3\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3?3.0?=?3.1?=?3.9?=3。
蛐蛐國最近蚯蚓成災了!隔壁跳蚤國的跳蚤也拿蚯蚓們沒辦法,蛐蛐國王只好去請神刀手來幫他們消滅蚯蚓。
蛐蛐國里現在共有 nnn 只蚯蚓(nnn 為正整數)。每只蚯蚓擁有長度,我們設第 iii 只蚯蚓的長度為 aia_iai? (i=1,2,…,ni=1,2,\dots,ni=1,2,…,n),并保證所有的長度都是非負整數(即:可能存在長度為 000 的蚯蚓)。
每一秒,神刀手會在所有的蚯蚓中,準確地找到最長的那一只(如有多個則任選一個)將其切成兩半。神刀手切開蚯蚓的位置由常數 ppp(是滿足 0<p<10 < p < 10<p<1 的有理數)決定,設這只蚯蚓長度為 xxx,神刀手會將其切成兩只長度分別為 ?px?\lfloor px \rfloor?px? 和 x??px?x - \lfloor px \rfloorx??px? 的蚯蚓。特殊地,如果這兩個數的其中一個等于 000,則這個長度為 000 的蚯蚓也會被保留。此外,除了剛剛產生的兩只新蚯蚓,其余蚯蚓的長度都會增加 qqq(是一個非負整常數)。
蛐蛐國王知道這樣不是長久之計,因為蚯蚓不僅會越來越多,還會越來越長。蛐蛐國王決定求助于一位有著洪荒之力的神秘人物,但是救兵還需要 mmm 秒才能到來……(mmm 為非負整數)
蛐蛐國王希望知道這 mmm 秒內的戰況。具體來說,他希望知道:
- mmm 秒內,每一秒被切斷的蚯蚓被切斷前的長度(有 mmm 個數);
- mmm 秒后,所有蚯蚓的長度(有 n+mn + mn+m 個數)。
蛐蛐國王當然知道怎么做啦!但是他想考考你……
輸入格式
第一行包含六個整數 n,m,q,u,v,tn,m,q,u,v,tn,m,q,u,v,t,其中:n,m,qn,m,qn,m,q 的意義見【問題描述】;u,v,tu,v,tu,v,t 均為正整數;你需要自己計算 p=u/vp=u / vp=u/v(保證 0<u<v0 < u < v0<u<v);ttt 是輸出參數,其含義將會在【輸出格式】中解釋。
第二行包含 nnn 個非負整數,為 a1,a2,…,ana_1, a_2, \dots, a_na1?,a2?,…,an?,即初始時 nnn 只蚯蚓的長度。
同一行中相鄰的兩個數之間,恰好用一個空格隔開。
保證 1≤n≤1051 \leq n \leq 10^51≤n≤105,0≤m≤7×1060 \leq m \leq 7 \times 10^60≤m≤7×106,0<u<v≤1090 < u < v \leq 10^90<u<v≤109,0≤q≤2000 \leq q \leq 2000≤q≤200,1≤t≤711 \leq t \leq 711≤t≤71,0≤ai≤1080 \leq a_i \leq 10^80≤ai?≤108。
輸出格式
第一行輸出 ?mt?\left \lfloor \frac{m}{t} \right \rfloor?tm?? 個整數,按時間順序,依次輸出第 ttt 秒,第 2t2t2t 秒,第 3t3t3t 秒,……被切斷蚯蚓(在被切斷前)的長度。
第二行輸出 ?n+mt?\left \lfloor \frac{n+m}{t} \right \rfloor?tn+m?? 個整數,輸出 mmm 秒后蚯蚓的長度;需要按從大到小的順序,依次輸出排名第 ttt,第 2t2t2t,第 3t3t3t,……的長度。
同一行中相鄰的兩個數之間,恰好用一個空格隔開。即使某一行沒有任何數需要輸出,你也應輸出一個空行。
請閱讀樣例來更好地理解這個格式。
樣例 #1
樣例輸入 #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樣例 #2
樣例輸入 #2
3 7 1 1 3 2 3 3 2樣例輸出 #2
4 4 5 6 5 4 3 2樣例 #3
樣例輸入 #3
3 7 1 1 3 9 3 3 2樣例輸出 #3
//空行 2提示
【樣例解釋1】
在神刀手到來前:333只蚯蚓的長度為3,3,23,3,23,3,2。
111秒后:一只長度為333的蚯蚓被切成了兩只長度分別為111和222的蚯蚓,其余蚯蚓的長度增加了111。最終444只蚯蚓的長度分別為(1,2),4,3(1,2),4,3(1,2),4,3。括號表示這個位置剛剛有一只蚯蚓被切斷
222秒后:一只長度為444的蚯蚓被切成了111和333。555只蚯蚓的長度分別為:2,3,(1,3),42,3,(1,3),42,3,(1,3),4。
3秒后:一只長度為444的蚯蚓被切斷。666只蚯蚓的長度分別為:3,4,2,4,(1,3)3,4,2,4,(1,3)3,4,2,4,(1,3)。
444秒后:一只長度為444的蚯蚓被切斷。777只蚯蚓的長度分別為:4,(1,3),3,5,2,44,(1,3),3,5,2,44,(1,3),3,5,2,4。
555秒后:一只長度為555的蚯蚓被切斷。888只蚯蚓的長度分別為:5,2,4,4,(1,4),3,55,2,4,4,(1,4),3,55,2,4,4,(1,4),3,5。
666秒后:一只長度為555的蚯蚓被切斷。999只蚯蚓的長度分別為:(1,4),3,5,5,2,5,4,6(1,4),3,5,5,2,5,4,6(1,4),3,5,5,2,5,4,6。
777秒后:一只長度為666的蚯蚓被切斷。101010只蚯蚓的長度分別為:2,5,4,6,6,3,6,5,(2,4)2,5,4,6,6,3,6,5,(2,4)2,5,4,6,6,3,6,5,(2,4)。所以,777秒內被切斷的蚯蚓的長度依次為3,4,4,4,5,5,63,4,4,4,5,5,63,4,4,4,5,5,6。777秒后,所有蚯蚓長度從大到小排序為6,6,6,5,5,4,4,3,2,26,6,6,5,5,4,4,3,2,26,6,6,5,5,4,4,3,2,2
【樣例解釋2】
這個數據中只有t=2t=2t=2與上個數據不同。只需在每行都改為每兩個數輸出一個數即可。
雖然第一行最后有一個666沒有被輸出,但是第二行仍然要重新從第二個數再開始輸出。
【樣例解釋3】
這個數據中只有t=9t=9t=9與上個數據不同。
注意第一行沒有數要輸出,但也要輸出一個空行。
【數據范圍】
思路
說實話,題目廢話真多,咳咳,這道題吧,在某谷上的標是提高+,省選-,不過吧其實沒那么難,只需要使用一個優先隊列即可,但是吧,又不完全是這樣,不要問我是怎么知道的,你需要使用一點小小的公式呢
-
對于兩條蚯蚓a,b, 若a先被切為x,y兩條蚯蚓(設lenx<leny), 而b后被切為u,v兩條蚯蚓(設lenu ≤lenv), 則在b被切完后的任意時刻, 均有lenx<lenu; leny < lenv
至于證明吧,就不需要了,相信大家!!(其實就是不想寫了
實現細節
記得double類型和int類型之間的轉換和關系
注意語言選c++14以下的
code
#include <bits/stdc++.h> using namespace std; double m,Q,u,v; int t,n; int cnt=0,tot=0,num=1; double p; int dd; int ans1[(int)7e6+5]; int a[(int)7e6+5]; queue<int>q1; queue<int>q2; queue<int>q3; inline int read() {int X = 0, F = 1;char C = getchar();while (C < '0' || C>'9') {if (C == '-') {F = -1;}C = getchar();}while (C >= '0' && C <= '9') {X = (X << 3) + (X << 1) + C - '0';C = getchar();}return X * F; } inline void write(int N) {if (N < 0) {putchar('-');N = -N;}if (N >= 10) {write(N / 10);}putchar(N % 10 + '0'); } inline int Get() {int x1=INT_MIN,x2=INT_MIN,x3=INT_MIN;if(!q1.empty())x1=q1.front();if(!q2.empty())x2=q2.front();if(!q3.empty())x3=q3.front();if(x1>=x2&&x1>=x3) {q1.pop();return x1;} else if(x2>=x3) {q2.pop();return x2;} else {q3.pop();return x3;} }//那個公式 int main() {n=read();m=read();Q=read();u=read();v=read();t=read();p=(double)u/v;for(register int i=1; i<=n; ++i) {ans1[i]=read();}sort(ans1+1,ans1+n+1, greater<int>());//排序后再壓入for(register int i=1;i<=n;i++){q1.push(ans1[i]);}int tag=0;for(register int i=1; i<=m; ++i) {int d=Get();d+=tag;a[i]=d;int tad=d*p;q2.push(tad-tag-Q);//截斷后的第一節q3.push(d-tad-tag-Q);//第二節tag+=Q;}for(register int i=t; i<=m; i+=t) {write(a[i]);printf(" ");}puts("");while(!q1.empty()||!q2.empty()||!q3.empty()) {int u=Get();if(num%t==0) {write(u+tag);//因為前面減了一個tag,現在加上printf(" ");}num++;}return 0; }總結
以上是生活随笔為你收集整理的#185. [NOIP2016 提高组] 蚯蚓题解的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 【OpenCV 例程 300 篇】105
- 下一篇: 机械键盘基础知识