TopCoder SRM 535 Div1 Medium: FoxAndBusiness

解法

topcoder.g.hatena.ne.jp

絶対ナップザックだと思ったら二分探索だった。

コード

import java.util.ArrayList;
import java.util.Collections;

public class FoxAndBusiness {
	public double minimumCost(int K, int W, int[] work, int[] cost) {
		int N = work.length;

		double high = 1e30, low = 0;
		double prevh = high, prevl = low;
		while (true) {
			double mid = (high + low) / 2;
			ArrayList<Double> cand = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				cand.add(work[i] * (mid - cost[i]));
			}
			Collections.sort(cand, Collections.reverseOrder());
			double sum = 0.0;
			for (int i = 0; i < K; i++) {
				sum += cand.get(i);
			}

			if (sum >= 3600. * K) {
				// もう少し小さくできる時
				high = mid;
			} else {
				low = mid;
			}

			// EPS状態
			if (prevh == high && prevl == low) {
				break;
			} else {
				prevh = high;
				prevl = low;
			}
		}
		return low * W;
	}
}