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

D. 货物均分

  • 传统题
  • 2000ms
  • 256MiB

货物均分

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 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 次操作。

全栈考核

未参加
状态
已结束
规则
IOI
题目
7
开始于
2026-11-8 19:00
结束于
2026-11-8 21:30
持续时间
2.5 小时
主持人
参赛人数
6