<問題>
①数字の順列が与えられる。
②魔法の数字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;
}
};
①数字の順列が与えられる。
②魔法の数字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;
}
};