問題
http://community.topcoder.com/stat?c=problem_statement&pm=11967&rd=15170
解き方
二分探索を用いればよい。
０が答えのときを含ませるには、lowを-1以下に設定する必要があることに注意。
コード
class KingdomAndTrees {
public:
bool ispossible(vector<int> h,int m){
int n=h.size();
h[0]=max(1,h[0]-m);
FORE(i,1,n){
if(h[i]+m<=h[i-1])return false;
h[i]=max(h[i-1]+1,h[i]-m);
}
return true;
}
int minLevel(vector<int> heights) {
long long low=-1,high=INT_MAX;
while(high-low>1){
int mid=(low+high)/2;
if(ispossible(heights,mid))high=mid;
else low=mid;
}
return high;
}
};
public:
bool ispossible(vector<int> h,int m){
int n=h.size();
h[0]=max(1,h[0]-m);
FORE(i,1,n){
if(h[i]+m<=h[i-1])return false;
h[i]=max(h[i-1]+1,h[i]-m);
}
return true;
}
int minLevel(vector<int> heights) {
long long low=-1,high=INT_MAX;
while(high-low>1){
int mid=(low+high)/2;
if(ispossible(heights,mid))high=mid;
else low=mid;
}
return high;
}
};