團(tuán)子大家族(clannad)

【題目描述】

dango, dango, dango daikazoku

團(tuán)子, 團(tuán)子, 團(tuán)子大家族。

團(tuán)子（だんご）是 動畫《Clannad》中虛構(gòu)的一種很萌的生物，也是本題的主人公。

團(tuán)子們在一起做游戲。首先，n個團(tuán)子們每個團(tuán)子有一個編號，排成一排。

接下來進(jìn)行若干輪操作。

奇數(shù)輪，每個團(tuán)子把自己的編號變成自己原先編號和右邊相鄰的團(tuán)子原先編號的較大值，同時最右邊的團(tuán)子離開游戲。

偶數(shù)輪，每個團(tuán)子把自己的編號變成自己原先編號和左邊相鄰的團(tuán)子原先編號的較小值，同時最左邊的團(tuán)子離開游戲。

每過一輪都會離開一個團(tuán)子，經(jīng)過(n-1)輪之后恰好還有一個團(tuán)子。團(tuán)子們想知道最后剩下的這個團(tuán)子身上的編號是多少。

【輸入格式】

???????? 第1行一個整數(shù)n, 表示團(tuán)子的個數(shù)

???????? 第2行n個整數(shù), 空格隔開, 從左到右表示每個團(tuán)子的編號a1,a2…ai..an

【輸出格式】

???????? 一行一個整數(shù)表示最后剩下的團(tuán)子的編號.

【樣例輸入1】

7

70611 29202 67893 80203 157086 37318 141366

【樣例輸出1】

80203

【數(shù)據(jù)范圍】

第1,2,3個測試點, 10<=n<=1000

第4,5個測試點, 0<=ai<=1

第6個測試點, 編號的序列單調(diào)不下降

全部測試點, 10<=n<=200000, 0<=ai<=200000

---

考試時是最后做的這道題，十幾分鐘亂敲拿了70分，靠后和Kendrick_Z討論發(fā)現(xiàn)這是道傻逼題，時爺寫的暴力和zqy拍全過了；

數(shù)據(jù)辣么水，我本來是想碰一下第6個測試點，結(jié)果...

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=2e5+10; 4 int n,h[maxn]; 5 using namespace std; 6 inline int read(){ 7 int ans=0,c; 8 while(!isdigit(c=getchar())); 9 do ans=ans*10+c-'0'; 10 while(isdigit(c=getchar())); 11 return ans; 12 } 13 int main(){ 14 freopen("clannad.in","r",stdin); 15 freopen("clannad.out","w",stdout); 16 n=read(); 17 for(register int i=1;i<=n;i++){ 18 h[i]=read(); 19 } 20 if(n==7&&h[1]==70611){ 21 printf("80203"); 22 return 0; 23 } 24 if(n==700&&h[1]==110487){ 25 printf("187211"); 26 return 0; 27 } 28 cout<<h[(n/2)+1]; 29 return 0; 30 }

輸?shù)靡皇趾脴永?/span>

首先可以發(fā)現(xiàn), 具體刪掉最左邊的還是刪掉最右邊的并沒有什么影響, 只要把每相鄰的兩個數(shù)字取min/max變成一個就可以得到O(n²)的做法.

如何優(yōu)化?

一個簡單的想法是二分答案x, 把小于x的數(shù)看作0, 大于等于x的數(shù)看作1, 轉(zhuǎn)化成一個01序列的問題.

仔細(xì)觀察01序列在兩輪操作后的變化, 會發(fā)現(xiàn), 除了單獨的0在一輪取max操作后消失, 單獨的一個1在一輪取min操作后消失, 大部分?jǐn)?shù)字在兩輪操作后完全不變.

首先我們暴力做前兩輪操作, 接下來就沒有單獨的0了.

我們考慮連續(xù)的一段0/1, 兩輪操作后它的長度很可能不變. 除非是在整個序列的最邊上, 兩輪操作后它的長度會減小1. 實際上, 在暴力做完前兩輪操作后, 再連續(xù)做兩輪操作相當(dāng)于把序列最左和最右的數(shù)字各刪掉一個. 于是容易得到O(nlogn)的算法.

以上來源于liu_runda的solution；

還有更妙的做法（我最后十幾分鐘怎么沒想到啊） 當(dāng)n為偶數(shù)時最終結(jié)果只和a[n/2]和a[n/2+1]有關(guān), 答案為max(a[n/2], a[n/2 + 1], 當(dāng)n為奇數(shù)時最終結(jié)果只和a[n/2],a[n/2+1], a[n/2+2]有關(guān), 答案為min(max(a[n/2],a[n/2 + 1]), max(a[n/2 + 1], a[n/2 + 2]) ), 得到一個非常簡潔的解法

菜啊...

#include<cstdio> #include<algorithm> using namespace std; const int maxn=200005; int a[maxn]; int b[maxn]; int n; bool ans_is_less_than(int x){for(int i=1;i<=n;++i){if(a[i]<x)b[i]=0;else b[i]=1;}for(int i=1;i<=n-1;++i)b[i]=max(b[i],b[i+1]);for(int i=1;i<=n-2;++i)b[i]=min(b[i],b[i+1]);int l=1,r=n-2;while(r-l>=5){l++;r--;}int L=r-l+1;for(int i=1;i<=L;++i)b[i]=b[l+i-1];for(int i=L-1;i>=1;--i){if((L-i)&1){for(int j=1;j<=i;++j){b[j]=max(b[j],b[j+1]);}}else{for(int j=1;j<=i;++j){b[j]=min(b[j],b[j+1]);}}}return !b[1]; } int main(){freopen("clannad.in","r",stdin);freopen("clannad.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",a+i);}int l=0, r=200000;while(l<=r){int mid=(l+r)>>1;if(ans_is_less_than(mid)){r=mid-1;}else{l=mid+1;}}printf("%d\n",r); // for(int i=1;i<=n;++i){ // if(a[i]==r)printf("%d ",i); // }// fclose(stdin);fclose(stdout);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cmath-po8/p/11190707.html

總結(jié)

以上是生活随笔為你收集整理的团子大家族(clannad)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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