平衡点(Balance Point)

题目描述

给定一个由 $n$ 个整数组成的数列 $a_1, a_2, \cdots, a_n$，请为这个数列找到一个平衡点，使得平衡点左侧与右侧的力矩尽量接近。

若平衡点为 $a_k$，则左侧力矩定义为数列中下标小于 $k$ 的各个元素到 $a_k$ 的距离乘以这些元素大小的总和。同理，右侧力矩定义为数列中下标大于 $k$ 的每个元素到 $a_k$ 的距离乘以这些元素大小的总和。

例如 $n=6$，若选 $a_4$ 为平衡点，左力矩计算公式为：

$$L = a_1 \times (4-1) + a_2 \times (4-2) + a_3 \times (4-3)$$

右力矩计算公式为：

$$R = a_5 \times (5-4) + a_6 \times (6-4)$$

请找到一个最佳平衡点，并输出选择该点为平衡点时，左右力矩之差绝对值的最小值。

输入格式

第一行：单个整数表示 $n$；

第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

单个整数：表示在选择了最佳平衡点的前提下，两侧力矩之差绝对值的最小值。

样例输入 #1

4
1 2 3 4

样例输出 #1

0

说明: 3号位为平衡点

数据范围

• $0 \leq a_i \leq 1,000,000$；
• 对于 30% 的数据，$3 \leq n \leq 10,000$；
• 对于 60% 的数据，$3 \leq n \leq 50,000$；
• 对于 100% 的数据，$3 \leq n \leq 300,000$。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模 n≤10
2	15	9~11	Hack: 全0 / 全同值 / 极端差
3	30	12~20	中大规模 n≈1000~300000
4	25	21~25	随机回归