圖片加載可能有點(diǎn)慢，請(qǐng)?zhí)^題面先看題解，謝謝

Uva的題目還是很好的，比如這道，是一道比較好的思維題，代碼難度不大

首先處理一下偶數(shù)的情況，很簡(jiǎn)單，答案是相鄰兩個(gè)守衛(wèi)的禮物和的最大值

這兒請(qǐng) fhr 給出證明：
把物品排成一行，只要一個(gè)人從左邊開始取，下一個(gè)人從右邊開始取，以此類推，保證不會(huì)重復(fù)
fhr 這人平時(shí)雖然腦子不太好使，但這個(gè)證明還是不錯(cuò)的。

那么奇數(shù)的情況怎么辦呢，有一種策略是這樣的：
假設(shè)有 \(cnt\) 種物品，第一個(gè)人取第 \(1～a[1]\) 個(gè)，往后走，編號(hào)是偶數(shù)的人從前往后取，奇數(shù)從后往前取，中途必須保證相鄰兩人取的東西不同。
舉個(gè)栗子：
就拿樣例的第二組數(shù)據(jù)來說，\(a[]={2,2,2,2,2}\)，然后 \(cnt=5\) 。
在這樣的情況下，每個(gè)人取物品的情況分別為 {1,2}，{3,4}，{5,2}，{1,3}，{5,4}。

這個(gè)東西啊看起來不那么好處理，但是請(qǐng)注意，這道題是不需要輸出方案的，所以我們可以這樣：
\(cnt\) 可以通過二分得到，
記 \(l[i]\)，\(r[i]\)，表示第 \(i\) 個(gè)人，在 \(1~a[1]\) 和 \(a[1]+1~cnt\) 各取了多少件，顯然 \(l[1]=a[1]\)。
那么這樣，每個(gè)人都可以根據(jù)前一個(gè)人的 \(l\) 和 \(r\) 值算出自己的 \(l\) 和 \(r\)，判一下是否合法就行。

//made by Hero_of_Someone #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define il inline #define RG register using namespace std; il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }int n,ans,a[100010]; int l[100010],r[100010];il void init(){ ans=0;for(RG int i=1;i<=n;i++) a[i]=gi();for(RG int i=2;i<=n;i++) ans=max(ans,a[i]+a[i-1]); ans=max(ans,a[1]+a[n]); }il bool ck(int x){ RG int k=x-a[1]; l[1]=a[1];for(RG int i=2;i<=n;i++){if(!(i%2)) l[i]=min(a[i],a[1]-l[i-1]),r[i]=a[i]-l[i];else r[i]=min(a[i],k-r[i-1]),l[i]=a[i]-r[i];if(l[i]+r[i]>x) return 0;if(l[i]<0||r[i]<0) return 0;}if(l[n]>0) return 0;return 1; }il void work(){if(n==1){ printf("%d\n",a[1]); return ; }if(!(n%2)){ printf("%d\n",ans); return ; }RG int l=ans,r=l<<1;while(l<=r){RG int mid=(l+r)>>1;if(ck(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans); }int main(){ while(scanf("%d",&n)&&n){ init(); work(); } return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Hero-of-someone/p/7651589.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的[UVALive 3177] Beijing Guards的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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