← 返回题目列表

AtCoder · joi2018_yo_d

D. 水羊馆

中文机器翻译题面 查看原题

配点 : 100 点

問題文

水羊羹是将主要由红豆制成的豆沙倒入模具中并用琼脂使其硬化而制成的日式点心。现在,JOI君有一个长方体形状的水瓶。 JOI 今天你打算吃这个水羊羹作为零食。

这款水羊羹的切口都是垂直的。 它位于 N-1 部分。水羊羹的长度是多少? L_1 + L_2 + ... + L_N 和i 番目 (1 ≦ i ≦ N-1) 中断从左侧开始。 它位于 L_1 + L_2 + ... + L_i 。

这个水羊羹太大了,吃不完,所以JOI君会从水羊羹里面切开来吃。 1 我决定选择多个地点,沿着选定的切口切割水羊羹,然后将其切成多块。然而,如果碎片大小不均匀,看起来会很糟糕,所以我决定将它们切割成最大碎片和最小碎片之间的长度差异尽可能小。

找出长度最大的片段和长度最小的片段之间的最小长度差。

制約

  • 2 ≦ N ≦ 50
  • 1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)

入力

输入是按以下格式从标准输入给出的。

N
L_1
L_2
:
L_N

出力

最大块和最小块之间的长度差的最小值为 1 行上。

小課題 1 [10点]

  • N ≦ 15

小課題 2 [27点]

  • L_i ≦ 10 (1 ≦ i ≦ N)

小課題 3 [63点]

  • 没有额外的限制。

入力例 1

11
2
3
8
4
7
6
6
5
1
7
5

出力例 1

2

在此示例中,4 th 和 沿着第 7 次切割,长度 17, 19, 18 的 已知 3 可以切成两块。 此时最长的一块有长度 19 ,最短的一块就是长度 17 ,所以长度差是 2 变为。 由于这是最小值, 输出2 。


入力例 2

2
1
10

出力例 2

9

无论大小如何不均匀,它总是 1 需要切割多个部分。


入力例 3

5
5
5
5
5
5

出力例 3

0

在此示例中,水羊羹的尺寸完全相同。 5 可分为两块。