解いた問題

7/13/2011

SRM456 Div1 Medium

450
答えが実数だし、2分探索ってことに気付くのは難しくなかった。
class CutSticks {
public:
  double maxKth(vector <int> v, int C, int K) {

    double s = 0;
    double b = *max_element( ALL(v) );
    
    for(int loop = 1000; loop--; ){
      double c = (s + b) / 2.0;
      
      int cnt = 0;
      lli sum = 0;
      for(int i=0; i<v.size(); ++i){
        sum += (double)v[i] / c;
        cnt += c <= (double)v[i];
      }
      
      if( K <= sum && K - C <= cnt )s = c;
      else b = c;
    }

    return s;
  }
};

0 件のコメント :

コメントを投稿