解题思路

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

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

定义状态：

P3877.第2题-坐火车IV

1000ms

Tried: 657

Accepted: 160

Difficulty: 7

所属公司 : 华为

算法与标签>动态规划

题目内容

某旅行线路上有一辆有 $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

输出

说明

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

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

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

$[1] [6] [4]$

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

样例2

输入

5 2
7 2 5 10 8

输出

说明

$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$

输入

预期输出（选填）

解题思路

P3877.第2题-坐火车IV

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About