https://vjudge.net/contest/144453#problem/A
长城守卫
1 #include <iostream> 2 #include <stdio.h> 3 using namespace std; 4 const int maxn = 1e5+10; 5 int n, a[maxn], le[maxn], ri[maxn]; 6 int Max(int x, int y) {return x > y ? x : y; } 7 int Min(int x, int y) {return x < y ? x : y; } 8 bool ok(int x){ 9 le[1] = a[1], ri[1] = 0; 10 int y = x - a[1]; 11 for(int i = 2; i <= n; i++){ 12 if(i&1){ 13 ri[i] = Min(a[i], y - ri[i-1]); 14 le[i] = a[i] - ri[i]; 15 }else{ 16 le[i] = Min(a[i], a[1] - le[i-1]); 17 ri[i] = a[i] - le[i]; 18 } 19 } 20 if(le[n] == 0) return true; 21 else return false; 22 } 23 int main(){ 24 while(scanf("%d", &n)&&n){ 25 for(int i = 1; i <= n; i++) scanf("%d", a+i); 26 int L = -1, R = -1; 27 a[n+1] = a[1]; 28 for(int i = 1; i <= n; i++){ 29 L = Max(L, a[i]+a[i+1]), R = Max(R, a[i]*3); 30 } 31 if(n == 1) { 32 printf("%d ", a[1]); 33 continue; 34 } 35 if(n&1){ 36 while(L < R){ 37 int mid = (L+R) >> 1; 38 if(ok(mid)){ 39 R = mid; 40 }else{ 41 L = mid + 1; 42 } 43 } 44 } 45 printf("%d ", L); 46 } 47 return 0; 48 }
只有不断学习才能进步！