SRM 548 250pt : KingdomAndTrees

TopCoder

問題概要

正整数列Xが与えられる。Xの各要素を[max(1, X[i]-T), X[i]+T]に含まれる数で置き換えることができる。Xを狭義単調増加にするにはTは最低どれだけあればよいか求める問題。

考えたこととか

  • 見るからに二分探索。
  • 整数の二分探索は最近復習していて、開区間で考えるようにすればよい。
  • 上端が小さくなりすぎないように気をつける。
  • 割と綺麗にかけた。一発で全部通って幸せ。
  • チャレンジポイントは、上限大きくしすぎて(low + high)/2でオーバーフローとか…、あっ、これ大きい解が作れないからそれじゃ落とせないか。0が答えになるケースもサンプルに入ってるし、落とすの難しそうだな…。

acceptされたコード

#include <vector>
#include <algorithm>
using namespace std;


struct KingdomAndTrees {

	int minLevel(vector <int> heights) {
		int low = -1, high = (int)(1e9) + 10;
		for (;high - low > 1;) {
			int mid = (high + low) / 2;
			if (!canMake(heights, mid)) {
				low = mid;
			}
			else {
				high = mid;
			}
		}
		return high;
	}

	bool canMake(const vector<int>& heights, int x) {
		const int n = heights.size();
		int prev = 0;
		for (int i = 0; i < n; ++i) {
			if (heights[i] + x <= prev) {
				return false;
			}
			else {
				prev = max( prev + 1, heights[i] - x );
			}
		}
		return true;
	}

};