← 返回题目列表

AtCoder · awc0047_d

D. 蛋糕均分

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

分数: 400 分

问题陈述

高桥被分配了分发蛋糕的任务 N 孩子们。孩子们被编号了孩子 1,孩子 2, ..., 孩子 N 从左到右,他们站成一排。

目前,孩子 i 有 A_i 蛋糕。高桥想要调整蛋糕,让所有孩子都能吃到相同数量的蛋糕。

Takahashi 可以执行以下操作任意次数:

  • 选择两个相邻的子项(子项 j 和孩子 j+1,其中 1 \leq j \leq N-1),然后移动 1 蛋糕从其中一个到另一个。然而,孩子身上的蛋糕是不可能移走的。 0 蛋糕。

蛋糕总数不会因操作而改变。无法添加新蛋糕或丢弃蛋糕。

求使所有孩子持有的蛋糕数量相等所需的最少操作次数。如果蛋糕总数不能整除 N 并且不可能达到目标,输出 -1.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N
A_1 A_2 \cdots A_N
  • 第一行包含一个整数 N 代表孩子的数量。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表每个孩子拥有的蛋糕数量。

输出

在一行中输出使所有孩子的蛋糕数量相等所需的最少操作数。如果无法实现目标,则输出 -1.


示例输入 1

3
1 2 3

示例输出 1

2

示例输入 2

3
1 2 4

示例输出 2

-1

示例输入 3

5
0 0 0 0 10

示例输出 3

20