SRM 548 KingdomAndTrees
問題概要
数列xが与えられる.
x[i]を[max(1, x[i] - m), x[i] + m]の範囲で置き換えることができる.
xが単調増加になることを満たす時の最小のmを求める.
方針
二分探索でmを求める.
mで単調増加な数列が作れるかどうかは貪欲に求まる.
class KingdomAndTrees { bool C(vector <int>& heights, int m) { int prev = max(heights[0] - m, 1); for(int i = 1; i < heights.size(); i++) { if(heights[i] + m < prev + 1) return false; else prev = max(prev + 1, heights[i] - m); } return true; } public: int minLevel(vector <int> heights) { int left = 0, right = 1000000000, mid; while(left < right) { mid = (left + right) / 2; if(C(heights, mid)) right = mid; else left = mid + 1; } return left; } };