山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[Aizu Online Judge] 二分法を利用した最適解の計算 (ALDS1_4_D: Allocation)

二分法

二分探索はソート済の配列を探索するアルゴリズムとして有名ですが、数値計算で二分法というものがあります。

二分法は、解の範囲が既知のとき、範囲の中間値を解の候補として探索していく手法です。

高校数学まででは馴染みがないですが、入試でみかけるニュートン法の問題を解いたことがあるので、イメージはつきました。

ALDS1_4_D: Allocation

f:id:yamakasa3:20180520174839p:plain

割り当て | アルゴリズムとデータ構造 | Aizu Online Judge

この問題の肝は、最大積載量  P の候補をどのようにして決めるかということです。

 P の最大値は、荷物の最大重量×荷物の最大個数です。最小値は、荷物の最大重量です。

しかし、入力される値はソートされていないので、 P の最大値を制約の最大を取ると考えます。また、最小値は  0 として差し支えないです。

したがって、解の範囲が分かったので、この範囲を二分法を用いて解きます。

コード

import java.util.Scanner;

public class ALDS1_4_D {
    public static int n;
    public static int k;
    public static int []w;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = scan.nextInt();
        w = new int[n];
        for(int i = 0; i < n; i++) {
            w[i] = scan.nextInt();
        }
        scan.close();
        long ans = solve();
        System.out.println(ans);
    }
    public static int check(long p) {
        int i = 0;
        for(int j = 0; j < k; j++) {
            long s = 0;
            while(s + w[i] <= p) {
                s += w[i];
                i++;
                if(i == n) return n;
            }
        }
        return i;
    }
    public static long solve() {
        long left = 0;
        // 荷物の個数×1個当たりの最大重量
        long right = 100000 * 10000;
        long mid;
        while(right - left > 1) {
            mid = (left + right) / 2;
            int v = check(mid);
            if(v >= n) right = mid;
            else left = mid;
        }
        return right;
    }
}