解题思路

题意：将按 ID 递增排列的 N 个旅行团（人数为数组 P[1..N]）切分成 M 个连续段（每段对应一节车厢），每个旅行团整体必须在同一车厢。目标是让各车厢人数的最大值记为 X、最小值记为 Y，使 X - Y 最小，要求输出对应方案中的 X。

关键结论（直观且常用于竞赛）： 要让差异 X - Y 尽量小，首先必须把最大车厢人数 X 压到尽可能小。 一旦存在某个划分的最大值高于可实现的“最小可能最大段和”，我们就能找到一个最大值更小的划分，从而不会使差异变得更好。因此，最终输出的 X 等于把数组切成 M 段时的最小可能最大段和。这正是经典问题 “分割数组的最大值最小化（Split Array Largest Sum）”。

实现方法（算法组合：二分答案 + 贪心检查）：

1. 设搜索上下界：

   • 下界 L = max(P)（任一车厢都要容纳某个旅行团）。
   • 上界 R = sum(P)（全部放一节车厢）。

2. 二分中间值 mid，用贪心模拟在“单节车厢人数不超过 mid”的限制下，需要多少节车厢：

   • 从左到右累加，当加入下一个旅行团会超过 mid 时，就开新车厢。
   • 统计得到的车厢数 cnt。

3. 若 cnt > M，说明 mid 太小（车厢不够），上调下界；否则可行，收缩上界。

4. 迭代至收敛，得到的 L 即为最小可行的最大车厢人数 X。

说明：题目只要求输出 X，不必输出具体分段；而该 X 与题意中“最小化差异”的最优方案一致。

复杂度分析

• 时间复杂度：O(N log S)，其中 S = sum(P)。每次二分用一次线性贪心计数。
• 空间复杂度：O(1)（只用常量额外空间）。

代码实现

Python

# 题目：最小化车厢人数差异（输出最大车厢人数 X）
# 思路：二分答案 + 贪心计数
# 说明：ACM 风格，主函数中完成输入输出，核心逻辑写在外部函数中

import sys

def need_cars(limit, arr, M):
    """
    给定每节车厢人数上限 limit，计算贪心最少需要多少节车厢。
    若某个旅行团人数本身 > limit，则必不可行（但二分下界已保证不会发生）。
    """
    count = 1      # 至少一节车厢
    cur = 0
    for x in arr:
        if cur + x <= limit:
            cur += x
        else:
            count += 1
            cur = x
    return count

def solve(N, M, arr):
    left = max(arr)      # 下界：至少容纳最大旅行团
    right = sum(arr)     # 上界：全部放一节
    while left < right:
        mid = (left + right) // 2
        cnt = need_cars(mid, arr, M)
        if cnt > M:
            # 需要的车厢太多，说明上限太小
            left = mid + 1
        else:
            # 可以在不超过 M 节车厢的情况下装下，尝试压缩上限
            right = mid
    return left

def main():
    data = sys.stdin.read().strip().split()
    N, M = map(int, data[:2])
    P = list(map(int, data[2:2+N]))
    ans = solve(N, M, P)
    print(ans)

if __name__ == "__main__":
    main()

Java

// 题目：最小化车厢人数差异（输出最大车厢人数 X）
// 思路：二分答案 + 贪心计数
// 说明：ACM 风格，类名 Main，输入输出在 main 中完成，核心逻辑在外部静态方法中

import java.io.*;
import java.util.*;

public class Main {

    // 贪心计算在单节车厢上限为 limit 时需要的车厢数量
    static int needCars(long limit, int[] arr) {
        int cnt = 1;          // 至少一节车厢
        long cur = 0;
        for (int x : arr) {
            if (cur + x <= limit) {
                cur += x;
            } else {
                cnt++;
                cur = x;
            }
        }
        return cnt;
    }

    static long solve(int N, int M, int[] arr) {
        long left = 0, right = 0;
        for (int x : arr) {
            left = Math.max(left, x);   // 下界：最大旅行团人数
            right += x;                 // 上界：总人数
        }
        while (left < right) {
            long mid = (left + right) / 2;
            int cnt = needCars(mid, arr);
            if (cnt > M) {
                // 需要车厢数过多，说明上限偏小
                left = mid + 1;
            } else {
                // 可行，尝试减小上限
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] p1 = br.readLine().trim().split("\\s+");
        int N = Integer.parseInt(p1[0]);
        int M = Integer.parseInt(p1[1]);
        String[] p2 = br.readLine().trim().split("\\s+");
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(p2[i]);

        long ans = solve(N, M, arr);
        System.out.println(ans);
    }
}

C++

// 题目：最小化车厢人数差异（输出最大车厢人数 X）
// 思路：二分答案 + 贪心计数
// 说明：ACM 风格，主函数中读写，核心逻辑单独函数

#include <bits/stdc++.h>
using namespace std;

// 贪心计算在单节车厢上限为 limit 时需要的车厢数量
static int need_cars(long long limit, const vector<int>& a) {
    int cnt = 1;                 // 至少一节车厢
    long long cur = 0;
    for (int x : a) {
        if (cur + x <= limit) cur += x;
        else { ++cnt; cur = x; }
    }
    return cnt;
}

static long long solve(int N, int M, const vector<int>& a) {
    long long left = 0, right = 0;
    for (int x : a) {
        left = max<long long>(left, x);   // 下界：最大旅行团人数
        right += x;                        // 上界：总人数
    }
    while (left < right) {
        long long mid = (left + right) / 2;
        int cnt = need_cars(mid, a);
        if (cnt > M) {
            // 需要车厢数过多，上限偏小
            left = mid + 1;
        } else {
            // 可行，尝试压缩上限
            right = mid;
        }
    }
    return left;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if (!(cin >> N >> M)) return 0;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    cout << solve(N, M, a) << "\n";
    return 0;
}

题目内容

某旅行线路上有一辆有 $M$ 节车厢的列车，所有车厢中都没人，现有 $N$ 个旅行团需要搭乘该线路，其 $ID$ 为 ：$[0,N)$ 。请给出具体的乘坐方案，满足使得各车厢间的乘客数量差异最小。(说明：乘客最多的车厢中的人数记作 $X$ ，乘客最少的车厢中的人数记作 $Y$ ，需要满足 $X-Y$ 最小) 旅行团乘坐列车需要满足如下要求：

1.对于任意 $0<i<j<M$ ，车厢i中的任意旅行团的 $ID$ 小于车厢 $j$ 中任意旅行团的 $ID$ 。

2.同个车厢内的旅行团，他们的 $ID$ 是连续的。

3.同个旅行团的成员必须在一个车厢内。

注：当只有一个车厢时，该车厢的乘客数既是最大乘客数，也是最小乘客数

输入描述

第 $1$ 行：$N$ $M$，其中

• $N$ 是旅行团个数，范围是 $[1,1000]$

• $M$ 是车厢个数，范围是 $[1,N]$

第 $2$ 行：$P_1$ $P_2$ ... $P_N$ ，每个数字代表一个旅行团的成员个数，成员个数范围是 $[1,100000]$

输出描述

输出乘客最多的车厢中的人数 $X$

样例1

输入

3 3
1 6 4

输出

6

说明

$3$ $3$ ：有 $3$ 个旅行团，列车有 $3$ 节车厢

$1$ $6$ $4$ ：这 $3$ 个旅行团的成员个数分别是 $1$ $6$ $4$

每个车厢都有旅行团时车厢人数差异才可能最小，考虑以下 $1$ 种乘坐方案

• $[1] [6] [4]$

可知乘客最多的车厢中的人数是 $6$

样例2

输入

5 2
7 2 5 10 8

输出

18

说明

$5$ $2$ ：有 $5$ 个旅行团，列车有 $2$ 节车厢

$7$ $2$ $5$ $10$ $8$ ：这 $5$ 个旅行团的成员个数分别是 $7$ $2$ $5$ $10$ $8$

每个车厢都有旅行团时车厢人数差异才可能小，因此只考虑以下 $4$ 种乘坐方案

• $[7][2$ $5$ $10$ $8]$ ：$7$ 和 $25$ ，人数差异 $18$

• $[7$ $2][5$ $10$ $8]$ ：$9$ 和 $23$ ，人数差异 $14$

• $[7$ $2$ $5][10$ $8]$ ：$14$ 和 $18$ ，人数差异 $4$

• $[7$ $2$ $5$ $10][8]$ ：$24$ 和 $8$ ，人数差异 $16$

可知最好的方式是 $[7$ $2$ $5][10$ $8]$ ，其中乘客最多的车厢中的人数是 $18$