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); }
のように現在の最長のピースをさらに分割するという方法でよいらしい。何でかはまだわかっていない。