SRM 456 Div2 Hard CutSticks

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909

n本の棒の長さが与えられる。好きな棒を好きな長さにC回まで切ることができる。その時にK番目に長い棒の長さを最大化せよ。なおK本以上の棒が出来るまでは必ずカットを行う。

やりかた

にぶたん。ある長さを決めて、C回までのカットでその長さの棒をK番目以降にすることができるか否かを調べる。できるならちょっと長くしてみて、できないようならもうちょっと短くしてみる（という理解で合っているのか。。。）うーんできなかった。

class CutSticks {
public:
  double maxKth(vector <int> sticks, int C, int K) {
    double ub = 1e15;
    double lb = 0;
    for(int i = 0; i < 100; i++){
      double mid = (ub + lb) / 2;

      int longer = 0;
      int cnt = 0;
      for(int j = 0; j < (int)sticks.size(); j++){
	if(sticks[j] >= mid){
	  longer++;//一回もハサミを入れなくて良い時。
	  cnt += (int)sticks[j] / mid - 1;//stick[i]に条件を満たすようハサミを入れられる回数
	  if(cnt > C) cnt = C;
	}	
      }
      
      if(longer + cnt >= K) lb = mid; else ub = mid;
    }
    return lb;
  }
};

易しめの問題なのだろうけれどできませんでした。もういちどやるときにはできるように。