题目链接：http://codeforces.com/problemset/problem/463/B
题目意思：Caisa 站在 0 pylon 并且只有 0 energy，他需要依次跳过1 pylon、2 pylon，...直到最后的 n pylon，每个 pylon（第 i 个） 都有对应的 height 值 hi，而每当从第 i 个pylon 跳到第i+1个pylon的时候，energy会增加 hi-hi+1，当然这个增加值有可能是负数，此时的energy则会相应的减少，现在要确保 energy 在任何时刻都是一个非负数。Caisa 可以向任意的一个pylon 增加 height，每增加一个单元的 height就需要 1 dollar，问从第1个 pylon 跳到 第 n 个pylon，且energy 是 非负的情况下，需要的最少dollar是多少。
方法一：直接做，二分模拟（31ms）
// 二分
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std; const int maxn = 1e5 + ;
int h[maxn], n; bool check(int x)
{
if (x - h[] < )
return false;
int energy = x - h[];
for (int i = ; i < n-; i++)
{
energy += h[i] - h[i+];
if (energy < )
return false;
}
return true;
} int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i < n; i++)
scanf("%d", &h[i]);
int l = , r = maxn;
int ans = maxn;
while (l <= r)
{
int m = (l+r)>>;
if (check(m))
{
ans = min(ans, m);
r = m - ;
}
else
l = m + ;
}
printf("%d\n", ans);
}
return ;
}
方法二：
找出序列中的最大值即为答案（46ms，有点奇怪）。
因为任意一个pylon 和 这个最大值的差都为正数或者0（序列中有多个最大值），也就是energy 一定不会变为负数！！！次大值也是不行的，因为如果序列中 pylon 1 的值是负数，energy 就为负数了，不符合条件。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; int main()
{
int n, h;
while (scanf("%d", &n) != EOF)
{
int ans = ;
for (int i = ; i < n; i++)
{
scanf("%d", &h);
ans = max(ans, h);
}
printf("%d\n", ans);
}
return ;
}