SRM548 Div1 Easy

250

二分探索する。

bool ascending(vector<lli> H)
{
  for (int i = 1; i < H.size(); ++i) {
    if (H[i - 1] < H[i]) continue;
    return false;
  }
  return true;
}

bool solve(vector<lli> H, lli x)
{
  H[0] = max(1LL, H[0] - x);
  for (int i = 1; i < H.size(); ++i) {
    if (H[i - 1] < H[i]) {
      H[i] = max(H[i - 1] + 1, H[i] - x);
    } else {
      H[i] = min(H[i - 1] + 1, H[i] + x);
    }
  }

  return ascending(H);
}

class KingdomAndTrees {
public:
  int minLevel(vector <int> H_)
  {
    vector<lli> H;
    for (int i = 0; i < H_.size(); ++i) {
      H.push_back(H_[i]);
    }

    if (ascending(H)) return 0;

    lli small = 0, large = 1000000000;
    while (small + 1 < large) {
      lli mid = (small + large) / 2LL;
      if (solve(H, mid)) large = mid;
      else small = mid;
    }
    return large;
  }
};