?

【NOIP2016】蚯蚓

?

?

話說(shuō)去年這個(gè)題 我用priority_queue亂搞 結(jié)果慘不忍睹?

q=0時(shí)送了50分 結(jié)果~~~~(>_<)~~~~ ?

每次彈出最長(zhǎng)的蚯蚓 把它切開(kāi) 在放回隊(duì)列?

這個(gè)應(yīng)該都能想到?

只不過(guò)除了被切的蚯蚓 其他蚯蚓每秒都會(huì)增長(zhǎng)?

所以 我們可以用一個(gè)變量來(lái)記錄增量

每次我們只彈出 隊(duì)列元素最大值 把它加上增長(zhǎng)變量 再去切它

?

并且保證隊(duì)列里的元素都是減掉了增量的?

注意 因?yàn)榍械脮r(shí)候蚯蚓不會(huì)變長(zhǎng) 所以放入隊(duì)列的時(shí)候還要減去當(dāng)前一秒增長(zhǎng)的長(zhǎng)度?

這個(gè)題 數(shù)據(jù)比較大 所以用priority_queue會(huì)超時(shí) 我寫(xiě)priority_queue 只拿了75分?

?

1 #include <cmath> 2 #include <queue> 3 #include <cstdio> 4 #include <cctype> 5 #include <algorithm> 6 7 const int MAXN=5*1e7+10; 8 9 int n,m,u,v,t,q,tag; 10 11 std::priority_queue<int> Q; 12 13 inline void read(int&x) { 14 int f=1;register char c=getchar(); 15 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 16 for(;isdigit(c);x=x*10+c-48,c=getchar()); 17 x=x*f; 18 } 19 20 int hh() { 21 read(n);read(m);read(q); 22 read(u);read(v);read(t); 23 for(int x,i=1;i<=n;++i) read(x),Q.push(x); 24 double p=(double)u/v; 25 for(int i=1;i<=m;++i) { 26 int now=Q.top();Q.pop(); 27 int L1=floor(p*(now+tag)); 28 int L2=(now+tag)-L1; 29 Q.push(L1-tag-q); 30 Q.push(L2-tag-q); 31 if(i%t==0) printf("%d ",now+tag); 32 tag+=q; 33 } 34 printf("\n"); 35 for(int i=1;i<=n+m;++i) { 36 int L=Q.top();Q.pop(); 37 if(i%t==0) printf("%d ",L+tag); 38 } 39 printf("\n"); 40 return 0; 41 } 42 43 int sb=hh(); 44 int main(int argc,char**argv) {;} priority_queue

?

正解是用三個(gè)隊(duì)列模擬過(guò)程?

一個(gè)隊(duì)列存儲(chǔ)原始蚯蚓 一個(gè)存儲(chǔ)切了一半的蚯蚓 另一個(gè)存儲(chǔ)另一半蚯蚓?

每個(gè)蚯蚓在每一秒都會(huì)增長(zhǎng)?

當(dāng)前蚯蚓被切以后 切成的兩半分別都要小于對(duì)應(yīng)隊(duì)列的最小值

換句話說(shuō) 后兩個(gè)隊(duì)列都是單調(diào)遞減的?

因?yàn)?我們每次取出當(dāng)前最長(zhǎng)的蚯蚓 加上累積的長(zhǎng)度?

切開(kāi)之后 再減去累積的長(zhǎng)度 在減去一個(gè)q放入隊(duì)列與其他數(shù)保持同步 ? 也就是這一秒他沒(méi)有增長(zhǎng)

可以看出整個(gè)操作沒(méi)有加法操作 我們只是把一個(gè)蚯蚓切開(kāi)后放入隊(duì)列 這樣顯然 ?后切開(kāi)的蚯蚓的長(zhǎng)度小于之前切開(kāi)的蚯蚓的長(zhǎng)度

顯然 隊(duì)列是單調(diào)的?

當(dāng)前蚯蚓最大值從三個(gè)隊(duì)列的隊(duì)首取就好了

ps:不敢相信double了 在UOJ上被hack 就是double惹的禍?

1 #include <cmath> 2 #include <cstdio> 3 #include <cctype> 4 #include <algorithm> 5 6 typedef long long LL; 7 const int INF=0x7fffffff; 8 const int MAXN=10000010; 9 10 int n,m,u,v,t,q,tag; 11 12 int t1,h1,t2,h2,h3,t3; 13 14 int q1[MAXN],q2[MAXN],q3[MAXN],q4[MAXN]; 15 16 inline void read(int&x) { 17 int f=1;register char c=getchar(); 18 for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar()); 19 for(;isdigit(c);x=x*10+c-48,c=getchar()); 20 x=x*f; 21 } 22 23 inline bool cmp(int a,int b) {return a>b;} 24 25 inline int get() { 26 int N1=-INF,N2=-INF,N3=-INF; 27 if(h1<t1) N1=q1[h1]; 28 if(h2<t2) N2=q2[h2]; 29 if(h3<t3) N3=q3[h3]; 30 if(N1>=N2&&N1>=N3) {++h1;return N1;} 31 if(N2>=N1&&N2>=N3) {++h2;return N2;} 32 if(N3>=N2&&N3>=N1) {++h3;return N3;} 33 } 34 35 int hh() { 36 read(n);read(m);read(q);read(u);read(v);read(t); 37 for(int x,i=1;i<=n;++i) read(x),q1[t1++]=x; 38 std::sort(q1,q1+t1,cmp); 39 // double p=(double)u/v; 40 for(int i=1;i<=m;++i) { 41 int now=get(); 42 LL L1=(LL)u*(now+tag)/v; 43 LL L2=(LL)(now+tag)-L1; 44 q2[t2++]=L1-tag-q; 45 q3[t3++]=L2-tag-q; 46 if(i%t==0) printf("%d ",now+tag); 47 tag+=q; 48 } 49 printf("\n"); 50 for(int i=1;i<=n+m;++i) { 51 int now=get(); 52 if(i%t==0) printf("%d ",now+tag); 53 } 54 printf("\n"); 55 return 0; 56 } 57 58 int sb=hh(); 59 int main(int argc,char**argv) {;} 隊(duì)列模擬

?

轉(zhuǎn)載于:https://www.cnblogs.com/whistle13326/p/7582371.html

總結(jié)

以上是生活随笔為你收集整理的【NOIP2016】蚯蚓 --队列模拟的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。