SRM548 DIV2 -500points

<問題>
①数字の順列が与えられる。
②魔法の数字Lを使うことで、それぞれの数字からLを引く、または足すことができる。
③このとき、与えられた数字の順列を昇順にするために必要な最小のLを返す。

<解き方>
二分探索で解けることがわかれば、の問題でした。

終了条件の設定を間違えると無限ループが続いてしまったり、
答えがlowかhighのどちらかの判定を加えなければいけなくなります。

そこで答えを満たす時はmidを範囲に加えて、
満たさないときはlow=mid+1とmidを範囲に加えないことで
low<highの条件で収束することができます。

<コード>
class KingdomAndTrees {

bool f(vector<int> h, int x){
int prev=0;
FORE(i,0,(int)h.size()){
if(h[i]+x<=prev)return false;
prev=max(prev+1,h[i]-x);
}
return true;
}

public:

int minLevel(vector<int> heights) {
int low=0,high=1000000000;
while(high-low>0){
int mid=(low+high)/2;
if(f(heights,mid))high=mid;
else low=mid+1;
}
return high;
}
};

Share this

Related Posts

Previous
Next Post »