SRM421

250

二分探索。

500

異なる長さの n<=50個のケーキをmaxCut回まで切っていいとき最短のピースと最長のピースの長さの差が最小になるようにしろという問題。
とりあえず、切るときは等分割にすればよいというのは分かったのだが、そこから最大の長さのピースの部分を固定してとか考えていたら50^2 * 10^5 = 25 * 10^7でJavaだと終わらないよなと思っていた。

あとであっている人のコードを見たところ

    int cutNums[] = new int[n];
    double pieceSize[] = new double[n];
    for(int i = 0 ; i < n ; i++)
      pieceSize[i] = weights[i];    
    for(int i = 1 ; i <= maxCuts ; i++){
      int mi = maxIndex(pieceSize);
      cutNums[mi]++;
      pieceSize[mi] = weights[mi] / (cutNums[mi] + 1.0);
    }

のように現在の最長のピースをさらに分割するという方法でよいらしい。何でかはまだわかっていない。