解题思路

本题需将 $N$ 个旅行团（成员数存于数组 $P[0\dots N-1]$）按 ID 连续分配到恰好 $M$ 节非空车厢中，满足各车厢乘客总数（连续段和）的最大值 $X$ 与最小值 $Y$ 的差异 $X-Y$ 最小，并输出该最优方案下的 $X$。

采用动态规划算法解决。 首先预处理前缀和数组 $prefix[0\dots N]$，其中 $prefix[i]$ 表示前 $i$ 个旅行团的总人数（$prefix[0]=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$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写