华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程
目录
题目
思路
Code
题目
题目内容：
园长阿姨手里捧着 A 个苹果，分量各不相同，从左到右的重量记作 g1, g2, …, gA。班里有 B 个小朋友，按学号从前往后站成一行。这些苹果要顺着站位发下去，规则有两条：
1. **不许剩下**：每个人至少领一个，苹果也要全部发出去。
2. **尽量匀一些**：每个人领到的分量之和要彼此靠近。
请给出一个最小的数。它是所有发法里，各人拿到的总重量中最大的那一份，再把这个最大份压到最低。
换句话说，每种发法先记下最沉的那一份，再在这些记录当中取最小的一个。
苹果必须维持现在的左右次序，只能从左往右切成 B 段连续苹果。第 1 段交给站在最前的小朋友，后面各段按站位依次往后交。不相邻的苹果不能抽出来交给同一个人。
举个例子。三个苹果重量是 2, 5, 1，发给 2 个小朋友。切成 [2] 与 [5,1]，两份是 2 和 6，最沉的是 6；切成 [2,5] 与 [1]，两份是 7 和 1，最沉的是 7。所以最低能压到 6。
## 输入描述
第一行给出两个整数 A 和 B。A 是苹果有多少个，B 是小朋友有多少人。
第二行给出 A 个整数 g1, g2, …, gA，按从左到右的次序写每个苹果的重量。
数据范围：
- 1 ≤ A ≤ 103
- 1 ≤ B ≤ A
- 1 ≤ gt ≤ 102
## 输出描述
只写出一个整数，表示最沉那一份能够压到的最小重量。
样例1
输入：
4 3 4 1 5 2输出：
5说明：要切成 3 段，只能在相邻苹果之间下刀。
[4] [1] [5,2]，三份是 4、1、7，最沉 7。
[4] [1,5] [2]，三份是 4、6、2，最沉 6。
[4,1] [5] [2]，三份是 5、5、2，最沉 5。
最低能压到 5，对应最后一种切法。
思路
整体思路：这是经典的"按顺序切分使最大段最小"问题，用二分答案加贪心判定。最沉一段的重量上限 L 具有单调性，L 越大越容易切，因此二分最小的可行 L；判定时从左往右贪心装袋，看最少需要几段。
1. 二分区间取 [最重苹果重量, 全部总重]：下界是因为单独一段也要装下最重的那只，上界对应只切成一段的情形。
2. 判定函数 packable(limit)：从左往右扫，当前段能装就装；若再放一只苹果会超过 limit，就新开一段并从这只苹果重新累加；若某只苹果自己就比 limit 重，直接判不可行。
3. 扫完后统计出的段数 used 若不超过人数 B，则 limit 可行。贪心"能装就装"的段数是该上限下的最少段数：提前切开只会浪费剩余容量，苹果顺序又不能调，段数不会更少。
4. 正数重量下，实际切分若少于 B 段，总能再补几刀把某些段切开，最沉段只会更轻或不变，所以"段数不超过 B"与"恰好切成 B 段"求出的最小最沉份相同，无需强制恰好 B 段。
5. 二分收敛后 low 就是最沉一段能压到的最小重量，直接输出。
复杂度：二分 O(log S) 轮，S 是总重量（不超过 A×100），每轮贪心 O(A)，总时间 O(A log S)，额外空间 O(A)。关键坑点：单只苹果比上限还重时必须立即判失败；贪心判定用"段数不超过 B"而不是"恰好 B 段"；重量全为正，上面的等价性才成立。
Code
C++
#include <bits/stdc++.h> using namespace std; int main() { // 读入苹果个数 A 和小朋友人数 B int a, b; if (scanf("%d %d", &a, &b) != 2) return 0; vector<long long> w(a); long long total = 0, heaviest = 0; for (int i = 0; i < a; i++) { scanf("%lld", &w[i]); total += w[i]; heaviest = max(heaviest, w[i]); } // 判断每段重量都不超过 limit 时最少需要几段，段数不超过 b 即可行 auto packable = [&](long long limit) { long long used = 1, acc = 0; for (int i = 0; i < a; i++) { if (w[i] > limit) return false; // 单只就超限，上限不可行 if (acc + w[i] > limit) { used++; // 再放这只就超限，新开一段 acc = w[i]; } else { acc += w[i]; } } return used <= (long long)b; }; // 二分最小可行上限：下界是最重苹果，上界是总重 long long low = heaviest, high = total; while (low < high) { long long mid = low + (high - low) / 2; if (packable(mid)) high = mid; else low = mid + 1; } printf("%lld\n", low); return 0; }Java
import java.io.*; import java.util.*; public class Solution { // 判断每段重量都不超过 limit 时最少需要几段，段数不超过 groups 即可行 static boolean packable(int[] w, long groups, long limit) { long used = 1, acc = 0; for (int x : w) { if (x > limit) return false; // 单只就超限，上限不可行 if (acc + x > limit) { used++; // 再放这只就超限，新开一段 acc = x; } else { acc += x; } } return used <= groups; } public static void main(String[] args) throws IOException { // 一次性读入所有输入再切词，避免逐行读太慢 DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16)); int a = nextInt(in); int b = nextInt(in); int[] w = new int[a]; long total = 0, heaviest = 0; for (int i = 0; i < a; i++) { w[i] = nextInt(in); heaviest = Math.max(heaviest, w[i]); total += w[i]; } // 二分最小可行上限：下界是最重苹果，上界是总重 long low = heaviest, high = total; while (low < high) { long mid = low + (high - low) / 2; if (packable(w, b, mid)) high = mid; else low = mid + 1; } StringBuilder sb = new StringBuilder(); sb.append(low).append('\n'); System.out.print(sb); } // 手写快读：跳过空白后按位拼整数（本题输入无负号） static int nextInt(DataInputStream in) throws IOException { int c = in.read(); while (c == ' ' || c == '\n' || c == '\r' || c == '\t') c = in.read(); int v = 0; while (c >= '0' && c <= '9') { v = v * 10 + (c - '0'); c = in.read(); } return v; } }Go
package main import ( "bufio" "os" "strconv" ) // 判断每段重量都不超过 limit 时最少需要几段，段数不超过 groups 即可行 func packable(w []int64, groups int64, limit int64) bool { used, acc := int64(1), int64(0) for _, x := range w { if x > limit { return false // 单只就超限，上限不可行 } if acc+x > limit { used++ // 再放这只就超限，新开一段 acc = x } else { acc += x } } return used <= groups } func main() { // 用 bufio.Reader 手动切词读入，避免 Scanner 缓冲区不够 reader := bufio.NewReader(os.Stdin) writer := bufio.NewWriter(os.Stdout) defer writer.Flush() readInt := func() int64 { var neg bool c, err := reader.ReadByte() for err == nil && (c == ' ' || c == '\n' || c == '\r' || c == '\t') { c, err = reader.ReadByte() } if c == '-' { neg = true c, _ = reader.ReadByte() } v := int64(0) for err == nil && c >= '0' && c <= '9' { v = v*10 + int64(c-'0') c, err = reader.ReadByte() } if neg { v = -v } return v } a := readInt() b := readInt() w := make([]int64, a) var total, heaviest int64 for i := range w { w[i] = readInt() if w[i] > heaviest { heaviest = w[i] } total += w[i] } // 二分最小可行上限：下界是最重苹果，上界是总重 low, high := heaviest, total for low < high { mid := low + (high-low)/2 if packable(w, b, mid) { high = mid } else { low = mid + 1 } } writer.WriteString(strconv.FormatInt(low, 10)) writer.WriteByte('\n') }C
#include <stdio.h> #include <stdlib.h> /* 判断每段重量都不超过 limit 时最少需要几段，段数不超过 b 即可行 */ static int packable(const long long *w, int n, long long limit, long long b) { long long used = 1, acc = 0; for (int i = 0; i < n; i++) { if (w[i] > limit) return 0; /* 单只就超限，上限不可行 */ if (acc + w[i] > limit) { used++; /* 再放这只就超限，新开一段 */ acc = w[i]; } else { acc += w[i]; } } return used <= b; } int main(void) { /* 读入苹果个数 A 和小朋友人数 B */ int a, b; if (scanf("%d %d", &a, &b) != 2) return 0; long long *w = (long long *)malloc(sizeof(long long) * (size_t)a); long long total = 0, heaviest = 0; for (int i = 0; i < a; i++) { scanf("%lld", &w[i]); if (w[i] > heaviest) heaviest = w[i]; total += w[i]; } /* 二分最小可行上限：下界是最重苹果，上界是总重 */ long long low = heaviest, high = total; while (low < high) { long long mid = low + (high - low) / 2; if (packable(w, a, mid, (long long)b)) high = mid; else low = mid + 1; } printf("%lld\n", low); free(w); return 0; }Python
import sys def min_peak(weights, groups): # 把 weights 按原顺序切成恰好 groups 段，返回"最沉一段"的最小可能值。 # 参数 weights 是各苹果重量列表，groups 是段数（小朋友人数）。 def packable(limit): # 判断能否让每一段重量都不超过 limit，能返回 True。 used = 1 acc = 0 for w in weights: if w > limit: # 单只苹果就比上限沉，这个上限肯定不行。 return False if acc + w > limit: # 当前段再放这只就超限，只能新开一段。 used += 1 acc = w else: acc += w # 段数不超过人数即可行；正重量下少切的段总能再补刀，不影响答案。 return used <= groups # 最沉一段至少装下最重的苹果，至多是全部总重（切成一段）。 low, high = max(weights), sum(weights) while low < high: mid = (low + high) // 2 if packable(mid): high = mid else: low = mid + 1 return low def main(): data = sys.stdin.read().split() a, b = int(data[0]), int(data[1]) weights = [int(x) for x in data[2:2 + a]] print(min_peak(weights, b)) if __name__ == "__main__": main()
