UVa12032

UVa12032
2分探索

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()

typedef long long int lli;

using namespace std;

const int N = 100000 + 1;
int h[N];

bool sim(int k, int n)
{
  for (int i = 0; i + 1< n; ++i) {
    int diff = h[i + 1] - h[i];
    if (k < diff) return false;
    k -= diff == k;
  }
  return true;
}

int main(int argc, char *argv[])
{
  int tc;
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;    
    for (int i = 0; i < n; ++i) {
      cin >> h[i + 1];
    }
    ++n;

    int s = 0;
    int b = 10000000 + 1;
    while (s + 1 < b) {
      int c = (s + b) / 2;
      if (sim(c, n)) b = c;
      else s = c;
    }
    static int cnt = 0;
    cout << "Case " << ++cnt << ": " << b << endl;
  }
  return 0;
}