有 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);