🎯

【Java】二分探索3

に公開
Java
初心者
tech

例題

サイズnの昇順にソートされた配列aがあります。a[0] ~ a[n-1]の長さのパイプからk本以上切り出すことができる整数単位での最大の長さを求めよ。

例題の値

n = 5
k = 6
a = [1, 2, 3, 4, 5]

例題の答え

長さが2の時、k = 6本のパイプを切り出すことができる。
要素1÷長さ2=0本、要素2÷長さ2=1本、要素3÷長さ2=1本、要素4÷長さ2=2本、要素5÷長さ2=2本の合計6本。

アルゴリズム

  • 切り出すことができる最大の長さの求め方
    • 長さxを固定
    • 長さxのパイプは各要素毎にa[i] / x（切捨）本だけ切り出せる
    • a[i] / xの和が最大本数
  • 二分探索の適用
    • 長さxのパイプをk本以上切り出せる→長さxをもっと長くできる（短い側の探索不要）
    • 長さxのパイプをk本切り出せない→長さxを短くしないといけない（長い側の探索不要）
  • 二分探索による解法
    • 境界の左端l = 0、境界の右端r = 101（最大長より大きい値）として、二分探索を開始
    • r - l == 1になるまで境界の位置を二分探索 → r - l != 1の間は探索を続ける
    • 中央の境界、かつ、切り出すパイプの長さである変数mid を (l + r) / 2（切り捨て）とする
    • 切り出せるパイプの本数をカウントする変数numを0で初期化
    • iを0からn-1までループさせ、変数numにa[i] / midの和を代入
    • 変数numがk以上なら、短い側の探索が不要なので、lをmidに更新
    • 変数numがk未満なら、長い側の探索が不要なので、rをmidに更新
    • 最終的に変数lに条件を満たす最大のパイプの長さが格納されるので、lを出力

コード例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt(), k = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        // 境界の左端 l を 0 で、境界の右端 r を 101 で初期化
        int l = 0, r = 101;

        // r - l が 1 とならない間
        while (r - l != 1) {
            // 中央の境界、かつ、切り出すパイプの長さである mid に (l + r) / 2 を代入
            int mid = (l + r) / 2;
            // 切り出せるパイプの本数をカウントする num を 0 で初期化
            int num = 0;

            // i を 0 から n - 1 までループさせて
            for (int i = 0; i < n; i++) {
                // num に a[i] / mid を代入
                num += a[i] / mid;
            }
            // num が k 以上なら
            if (num >= k) {
                // l を mid に更新
                l = mid;
            // そうでないなら
            } else {
                // r を mid に更新
                r = mid;
            }
        }
        // l を出力
        System.out.println(l);
    }
}

Discussion