LA 3177 长城守卫(推理+二分)
训练指南书上推理是对的，但书上代码个人觉得是有问题的，但却能够AC，真是不解。
#include <iostream>using namespace std;int a[100005],elft[2],rig[2],n;int OK(int ans){int x=a[1],y=ans-a[1],id=0,i;elft[0]=x; rig[0]=0;for(i=2;i<=n;i++){id=!id;if(i&1){rig[id]=min(y-rig[!id],a[i]);elft[id]=a[i]-rig[id];}else{elft[id]=min(x-elft[!id],a[i]);rig[id]=a[i]-elft[id];}}return elft[id]==0;}int main(int argc, char *argv[]){int i,L,R,M;while(cin>>n&&n){ L=R=0;for(i=1;i<=n;i++){cin>>a[i];L=max(L,a[i]+a[i-1]);R=max(R,a[i]*3);}L=max(L,a[1]+a[n]);if(n&1){while(L<R){M=(L+R)>>1;if(OK(M)) R=M; else L=M+1;}}cout<<L<<endl;}return 0;}