UVA - 1335 Beijing Guards

本文主要是介绍UVA - 1335 Beijing Guards，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：LRJ大白上的题目：点击打开链接

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 100050;int n,A[MAXN];
int Left[MAXN],Right[MAXN];int ok(int p){Left[1] = A[1];Right[1] = 0;for (int i = 2; i <= n; i++){if (i & 1){int ts = p - A[1] - Right[i-1];Right[i] = min(ts,A[i]);Left[i] = A[i] - Right[i];if (Left[i] + Left[i-1] > A[1])return 0;}else {int ts = A[1] - Left[i-1];Left[i] = min(ts,A[i]);Right[i] = A[i] - Left[i];if (Right[i] + Right[i-1] > p-A[1])return 0;}}return Left[n] < 1;
}int main(){while (scanf("%d",&n) != EOF && n){long long sum = 0,maxa = 0;for (int i = 1; i <= n; i++){scanf("%d",&A[i]);sum += A[i];if (maxa < A[i])maxa = A[i];}int ans = 0;if (n & 1){long long L = maxa,R = sum;while (L < R){int M = (L + R)>>1;if (ok(M))R = M;else L = M+1;}ans = L;}else {ans = A[1] + A[n];for (int i = 1; i < n; i++)if (A[i]+A[i+1] > ans)ans = A[i] + A[i+1];}printf("%d\n",ans);}return 0;
}

这篇关于UVA - 1335 Beijing Guards的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---