跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#X261108D. 货物均分

货物均分

题目描述

有 NN 个货位排成一行,第 ii 个货位有 AiA_i 箱货物。货物总数保证是 NN 的倍数。

一次操作可以从某个货位取出 任意正整数箱 现有货物,并把它们全部搬到一个相邻货位。一次操作只能跨越一对相邻货位,不能直接搬到更远的地方。中间货位的货物数量可以暂时为 0,但不能为负。

求使所有货位的货物数量相等所需的最少操作次数。注意,计算的是搬运操作次数,不是搬运的总箱数。

输入格式

第一行一个整数 NN。接下来给出 NN 个整数 A1,…,ANA_1,\ldots,A_N,用空白字符分隔。

输出格式

输出一个整数,表示最少操作次数。

数据范围与计分

1≤N≤1001\le N\le100,1≤Ai≤100001\le A_i\le10000,且 ∑Ai\sum A_i 能被 NN 整除。

本题满分 100 分,各测试点独立、等额计分。

样例 1

3
1 1 4
2

样例 2

4
1 3 3 1
2

样例说明

样例 1 可以先从第 3 个货位搬 2 箱到第 2 个货位,得到 1、3、2;再从第 2 个货位搬 1 箱到第 1 个货位,得到 2、2、2,共 2 次操作。

相关

在下列比赛中:

全栈考核