ファイルが n 個、1 番から n 番まで順にあり、i 番のファイルの大きさは wᵢ である。
これらのファイルを、容量がどれも C のバックアップディスク何枚かに番号の順に分けて入れる。
ディスク一枚には番号が連続したファイルだけを入れ、一枚に入れたファイルの大きさの合計は C を超えてはならない。
ファイルの順番を変えたり、一つのファイルを二枚に分けて入れたりはできない。
ディスクを d 枚以下使ってすべてのファイルを入れられる最小の整数 C を出力せよ。
一行目に n と d、二行目に w₁ … wₙ が空白区切りで与えられる。
6 3 3 2 2 4 1 4
6
4 2 1 1 1 10
10
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
C を 1 から一つずつ増やすと、合計（10¹³）まで行くこともあります。
容量が大きいほど必要なディスクは減るので「d 枚以下で入るか」は前が偽、後ろが真です。
そこで答えを二分探索します：真ん中 mid でディスクが何枚要るか数え、できれば hi = mid、できなければ lo = mid + 1。
枚数の数え方は貪欲法です — 今のディスクにまだ入れば入れ、あふれるなら新しいディスクへ移ります。
多くても 44 回 × n なのですぐ終わります。
罠は三つ：① 下の端は 1 ではなくいちばん大きいファイルです。
1 から探すと枚数の数え方が入らないファイルもそのディスクに入れてしまい、例 2 のように 10 より小さい答えが出ます。
② 合計は 10¹³ までなので Java・C#・C・C++ では long/long long が必要です。
C# の w.Sum() は int で足して OverflowException を出すので w.Sum(x => (long)x)、C++ の std::accumulate は初期値を 0LL にしてはじめて long long で足します。
Python はあふれず、JavaScript・TypeScript・Craykon は数が double なので 2^53（約 9×10¹⁵）以内なら正確です。
③ 枚数は 1 から数えます — 0 から数えると、いま入れている最後のディスクを落とします。
Craykon には整数の割り算がないので、真ん中は 数学.商(lo + hi, 2) で求めます。
def disks_needed(w, cap): """용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).""" disks, used = 1, 0 for x in w: if used + x > cap: disks += 1 used = 0 used += x return disks n, d = map(int, input().split())w = list(map(int, input().split())) # 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. '되는가'는 앞쪽이 거짓, 뒤쪽이 참이다.lo, hi = max(w), sum(w)while lo < hi: mid = (lo + hi) // 2 if disks_needed(w, mid) <= d: hi = mid else: lo = mid + 1print(lo)// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w, cap) { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} const [n, d, ...w] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);import { readFileSync } from "node:fs"; // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).function disksNeeded(w: number[], cap: number): number { let disks = 1; let used = 0; for (const x of w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} const [n, d, ...w]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이. 합은 10¹³까지라 2^53 안이다.let lo = Math.max(...w);let hi = w.reduce((s, x) => s + x, 0);while (lo < hi) { const mid = Math.floor((lo + hi) / 2); if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1;}console.log(lo);import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main { // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int disksNeeded(int[] w, long cap) { int disks = 1; long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int d = Integer.parseInt(st.nextToken()); int[] w = new int[n]; long lo = 0, hi = 0; // 합은 10¹³까지라 long st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) { w[i] = Integer.parseInt(st.nextToken()); lo = Math.max(lo, w[i]); hi += w[i]; } while (lo < hi) { long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } System.out.println(lo); }}using System;using System.Linq; class Program{ // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). static int DisksNeeded(int[] w, long cap) { int disks = 1; long used = 0; foreach (int x in w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks; } static void Main() { int d = int.Parse(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries)[1]); int[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); long lo = w.Max(); long hi = w.Sum(x => (long)x); // w.Sum()은 int로 더하다 OverflowException while (lo < hi) { long mid = lo + (hi - lo) / 2; if (DisksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } Console.WriteLine(lo); }}#include <algorithm>#include <iostream>#include <numeric>#include <vector> // 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).int disksNeeded(const std::vector<int>& w, long long cap) { int disks = 1; long long used = 0; for (int x : w) { if (used + x > cap) { disks++; used = 0; } used += x; } return disks;} int main() { int n, d; std::cin >> n >> d; std::vector<int> w(n); for (int& x : w) std::cin >> x; long long lo = *std::max_element(w.begin(), w.end()); long long hi = std::accumulate(w.begin(), w.end(), 0LL); // 0이 아니라 0LL: 시작값의 타입으로 더한다 while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disksNeeded(w, mid) <= d) hi = mid; else lo = mid + 1; } std::cout << lo << "\n";}#include <stdio.h> static int w[10000]; /* 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일). */static int disks_needed(int n, long long cap) { int disks = 1; long long used = 0; for (int i = 0; i < n; i++) { if (used + w[i] > cap) { disks++; used = 0; } used += w[i]; } return disks;} int main(void) { int n, d; long long lo = 0, hi = 0; /* 합은 10¹³까지라 long long */ scanf("%d %d", &n, &d); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); if (w[i] > lo) lo = w[i]; hi += w[i]; } while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (disks_needed(n, mid) <= d) hi = mid; else lo = mid + 1; } printf("%lld\n", lo); return 0;}// 용량이 cap인 디스크에 앞에서부터 들어가는 만큼 담으면 디스크가 몇 개 필요한가(cap >= 가장 큰 파일).필요한디스크(w, cap){ disks = 1; used = 0; それぞれ (x の中 w) { もし (used + x > cap) { disks += 1; used = 0; } used += x; } 返す disks;} 첫줄 = コンソール.数読み();d = 첫줄[1];w = コンソール.数読み();// 답은 가장 큰 파일 ~ 모든 파일 크기의 합 사이lo = 0;hi = 0;それぞれ (x の中 w){ lo = 数学.大きい方(lo, x); hi += x;}間 (lo < hi){ mid = 数学.商(lo + hi, 2); もし (필요한디스크(w, mid) <= d) { hi = mid; } でなければ { lo = mid + 1; }}コンソール.書く(lo);