SRM 548 div1 easy: KingdomAndTrees

問題

TopCoder Statistics - Problem Statement

n 本の木が与えられ, それぞれは高さ h[i] である。レベル X の魔法を使うと, それぞれの木の高さを, [max(1, h[i]-X), h[i]+X] の範囲に変化させることが出来る(ただし高さは整数にしなければならない)。この魔法を 1 回使うことによって, 木を狭義に単調増加させたい。
魔法レベルを最小化せよ。

解法

二分探索します。

x でOK かどうか判定する関数 ok(x) = (レベル x の魔法で足りるか？)は, h[i+1] > h[i] を満たす範囲で h[i+1] を最小化させるように魔法を打っていけば良いです。

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

class KingdomAndTrees {
public:
    int minLevel(vector <int> heights) {
        ll low = -1, high = 1ll<<55;
        while (high-low > 1) {
        	const ll med = (high+low)/2;
        	if (ok(med, heights)) high = med;
        	else low = med;
        }
        return (int)high;
    }
};