Circular Barn

题目描述

作为当代建筑的爱好者，农夫约翰建造了一个全新的谷仓，其形状是一个完美的圆。谷仓内部由一个包含 $n$ 个房间的环组成，这些房间沿着谷仓的周长按顺时针方向从 $1 \ldots n$ 编号（$3 \leq n \leq 100,000$）。每个房间都有通往相邻两个房间的门，同时也有一扇通往谷仓外部的门。 农夫约翰有 $n$ 头奶牛，他希望最终每个房间恰好有一头奶牛。然而奶牛有点迷糊，会在随机的门外排队，可能有多个奶牛排在同一个门外。具体来说，在房间 $i$ 的门外有恰好 $c_i$ 头奶牛排队，因此 $\sum c_i = n$。 为了管理赶牛过程，使得每个房间最终有一头奶牛，农夫约翰打算采用如下方法：每头奶牛从她最初排队的那扇门进入，然后沿顺时针方向在房间间行走，直到她到达一个合适的目的地。已知一头奶牛穿过 $d$ 扇门会消耗 $d^2$ 的能量，请确定将奶牛分配到各房间使得每个房间恰好有一头奶牛所需的最小总能量。

输入格式

第一行输入包含 $n$。接下来的 $n$ 行每行包含 $c_1 \ldots c_n$。

输出格式

请输出奶牛消耗的最小总能量。

10
1
0
0
2
0
0
1
2
2
2

33

提示

题目致谢：Brian Dean

标签: USACO|2016|Gold

来源

USACO|2016|Gold