1064 - けーぶるますたー 2012/10/01

Javaです。

1064 -- Cable master

問題文は読んでないです。
蟻の本 であったものベースでチャレンジ。自力で無理でした。
丸めで苦戦してしまいました。

 プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～
秋葉拓哉 岩田陽一 北川宜稔




二分探索で解くということらしいです。
mid = (low + high) / 2
といのがみそっぽいですね。

package p1064;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] ss = scanner.nextLine().split(" ");
        int N = Integer.parseInt(ss[0]);
        int K = Integer.parseInt(ss[1]);

        double[] fs = new double[N];
        double max = 1000000;
        List<Double> list = new ArrayList<Double>();
        for (int i = 0; i < fs.length; i++) {
            double f = Double.parseDouble(scanner.nextLine());
            max = max > f ? max : f;
            // System.out.println(f);
            list.add(f);
        }

        int check = 0;

        double ub = max;
        double lb = 0;

        while (true) {
            if (check++ > 50)
                break;
            double mid = (lb + ub) / 2.;
            double cnt = solve(list, mid);
            // System.out.printf("K:%d   cnt:%f   mid:%f lb:%f  ub:%f  %n", K,
            // cnt, mid, lb, ub);

            if (K > cnt) {
                ub = mid;
                continue;
            }
            if (K <= cnt) {
                lb = mid;
                continue;
            }
        }

        System.out.printf("%.2f%n", Math.floor(ub * 100) / 100);
    }

    static double solve(List<Double> list, double f) {
        double cnt = 0;
        for (double f2 : list) {
            cnt += Math.floor(f2 / f);
        }
        return cnt;

    }

}