TopCoder SRM 456 Div1 Medium CutSticks

問題

n本の棒があり、長さはそれぞれsticks[i]である。
これらの棒を最大C回切断した後で、K番目に長いものの長さの最大値を求めよ。

切断の前後で、棒の長さの和は等しく、切断した棒を再び切断することもできる。
また、最後の切断を終えた後で、棒はK本以上になっている必要がある。

制約条件

n≦50
sticks[i]≦10^9

方針

二分探索。

K番目に長いものの長さがL以上であることは、C回のカットで長さLの棒をK本作れることと同値。
よって長さLについて二分探索して、カットC回以下で棒をK本作れるかを見てやればよい。

ソースコード

class CutSticks {
  public:
  double maxKth(vector <int> sticks, int C, int K) {
    double lo=0,hi=1e12,mid;
    rep(i,100){
      mid=(lo+hi)/2;
      int cnt=0,cut=0;
      rep(j,sticks.size()){
        int t=max(0,(int)(sticks[j]/mid)-1);
        t=min(t,C-cut);
        cut+=t; cnt+=sticks[j]>=mid?t+1:0;
      }
      if(cnt>=K)lo=mid; else hi=mid;
    }
    return lo;
  }
};