新・アルゴリズムとデータ構造入門 Java編9:最大値を求める

import java.util.Scanner;

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();
        }

        // 変数 left, right をそれぞれ 0 と 10001 で初期化

        // 50 回繰り返すループを作成
        // 変数 mid に (left + right) / 2 を代入
        // 切り出せる本数を表す変数 num を 0 で初期化

        // i を 0 から n - 1 まで繰り返す
        // num に a[i] / mid の整数部分を足す

        // もし num が k 以上なら
        // left を mid で更新
        // そうでなければ
        // right を mid で更新

        // left を出力
    }
}

import java.util.Scanner;

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();
        }

        // 変数 left, right をそれぞれ 0 と 10001 で初期化

        // 50 回繰り返すループを作成
        // 変数 mid に (left + right) / 2 を代入
        // 切り出せる本数を表す変数 num を 0 で初期化

        // i を 0 から n - 1 まで繰り返す
        // num に a[i] / mid の整数部分を足す

        // もし num が k 以上なら
        // left を mid で更新
        // そうでなければ
        // right を mid で更新

        // left を出力
    }
}

import java.util.Scanner;

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();
        }

        // ここにコードを書く
    }
}

import java.util.Scanner;

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();
        }

        // ここにコードを書く
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「整数での二分探索」

整数 n, k と長さ n の配列 a が与えられるので、a[0] ~ a[n-1] の長さのパイプから k 本以上切り出すことができる整数単位での最大の長さを求めてください。
すでに入力を行うコードが実装されているので、コードを書き足して完成させてください。

入力される値

5 6
1 2 3 4 5

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃04:最大値を求める

レベルアップ問題集「二分探索メニュー」の「パイプを切り出そう」の問題を解いていきます。

二分探索の回数

今回の問題で求められている精度は 10^{-6} (0.000001) です。また、二分探索の初期範囲は 0.0 から 10001.0 です。
したがって、二分探索で狭めるべき範囲の大きさは約 10^{10} (≒ 10001.0 / 10^{-6}) 分の 1 になります。
これに対し底を 2 とする対数をとると、log_2(10^{10}) ≒ 33.22 となります。したがって、二分探索のループの回数は 34 回以上にすることで必要な精度を得ることができます。

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門 Java編9: 二分探索 > 最大値を求める

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：

5 6
1 2 3 4 5