← 返回题目列表

AtCoder · ddcc2020_qual_b

B. 铁棒切割

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

分数: 200 点

问题陈述

在 DISCO 工作的高桥正站在一根铁棍前。 酒吧有 N-1 凹口,将条分为 N 部分。 i从左边算起第一个部分的长度为 A_i 毫米。

高桥想要选择一个凹口,并将该点处的条切成长度相同的两部分。 然而,这可能不可能,所以他会多次执行以下操作 之前 他进行了剪辑:

  • 选择一个部分并将其展开,将其长度增加 1 毫米。执行此操作一次会产生费用 1 日元(日本的货币)。
  • 至少选择一段长度 2 毫米并收缩它,将其长度减少 1 毫米。执行此操作一次会产生费用 1 日元。

求出将钢筋切成相同长度的两部分之前所需的最低金额。

约束

  • 2 \leq N \leq 200000
  • 1 \leq A_i \leq 2020202020
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 A_3 ... A_N

输出

打印一个整数,表示将条切成相同长度的两部分之前所需的最低金额。


示例输入 1

3
2 4 3

示例输出 1

3

各部分的初始长度为 [2, 4, 3] (以毫米为单位)。高桥在进行以下操作后可以将钢筋平均切割 3 日元:

  • 缩小左侧第二个部分。现在各部分的长度是 [2, 3, 3].
  • 缩小左侧的第一部分。现在各部分的长度是 [1, 3, 3].
  • 缩小左侧第二个部分。现在各部分的长度是 [1, 2, 3],我们可以将左侧第二个凹口处的条形切割成长度的两部分 3 每个。

示例输入 2

12
100 104 102 105 103 103 101 105 104 102 104 101

示例输出 2

0