SRM548 Div1 Easy - KingdomAndTrees
問題
木がn本あり、i本目の高さはa[i]である
コストxの魔法を使うと各木の高さを0〜xだけ増やすか減らすことができる
aを競技単調増加にするために使う必要のある魔法の最小コストを求めよ
2 <= n <= 50
1 <= a[i] <= 10^9
解法
二分探索
使う魔法のコストを決めたとき、各木の高さは単調増加になる範囲でなるべく低くしていけばいい
class KingdomAndTrees { public: int minLevel(vector<int> a) { int n = a.size(), l = -1, r = 1<<30; while (r-l>1) { int m = (l+r)/2, b = 0, ok = 1; rep(i,n) { if (a[i]+m<=b) ok = 0; else b = max(b+1, a[i]-m); } (ok ? r : l) = m; } return r; } };