Circular Barn

题目描述

作为当代建筑的爱好者，农夫约翰建造了一个全新的谷仓，其形状为完美的圆形。谷仓内部由一个包含 $n$ 个房间的环组成，房间沿着谷仓周边按顺时针方向编号为 $1 \ldots n$（$3 \leq n \leq 1,000$）。每个房间都有通往左右相邻房间的门，此外还有一扇通向谷仓外部的门。 农夫约翰希望最终每个房间 $i$ 中正好有 $r_i$ 头奶牛（$1 \leq r_i \leq 100$）。为了有序地把奶牛赶进谷仓，他计划只解锁某一个房间的外部门，让奶牛从该门进入。每头奶牛随后沿顺时针方向穿过房间，直到到达一个合适的目的地。 农夫约翰希望选择一个解锁外部门的房间，使得所有奶牛合计行走的总距离最小。请确定在他选择最佳解锁房间的情况下，奶牛需要行走的最小总距离。单头奶牛行走的距离定义为她经过的内部门数量。

输入格式

第一行输入为 $n$。 接下来的 $n$ 行每行包含 $r_1 \ldots r_n$。

输出格式

请输出所有奶牛合计需要行走的最小总距离。

5
4
7
8
6
4

48

提示

在这个例子中，最优方案是让奶牛从需要 7 头奶牛的那个房间的门进入。 题目来源：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze