Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-07-22

KingdomAndTrees (SRM 548 Div2Medium, Div1Easy)

17:53 | KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder を含むブックマーク はてなブックマーク - KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder KingdomAndTrees (SRM 548 Div2Medium, Div1Easy) - capythm@TopCoder のブックマークコメント

問題概要

N本の木が直線上に立っている。木の高さを昇順になるようにしたい。

魔法使いは木の高さを-level~+levelの範囲で変化させることができる。

昇順にするための最小レベルはいくつか?

http://community.topcoder.com/stat?c=problem_statement&pm=11967

解法

二分探索を使います。

あるレベルの時に昇順にできるかどうかの判定方法(関数check)は以下のような感じです。

  • 木を先頭から見ていく。
  • 現在の木をできる限り低くする。ただし直前の木より+1は高くする。
  • 魔法を使った後の木の高さと元の木の高さを比較して、今のレベル以上必要だったらNG

ソースコード

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class KingdomAndTrees{
  bool check( vector<int> h, int lev ){
    int prev = 0;
    for( int i=0; i<h.size(); i++ ){
      int curr = max( prev+1, h[i]-lev );
      if( abs( curr - h[i] ) > lev ) return false;
      prev = curr;
    }
    return true;
  }
public:
  int minLevel(vector <int> heights){
    int lo=0,hi=1000000000,ret=-1;
    while( lo <= hi ){
      int mid = (lo+hi)/2;
      if( check( heights, mid ) ){
        ret = mid;
        hi = mid-1;
      } else {
        lo = mid+1;
      }
    }
    return ret;
  }
};