圆形牛棚（寒假每日一题 22）

圆形牛棚（寒假每日一题 22）

作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。

牛棚内部有 n n n 个房间，围成一个环形，按顺时针编号为 1... 1...n，所有相邻房间之间的距离均为 1 1 1。

每个房间都既有通向相邻两个房间的门，也有通向牛棚外部的门。

约翰想让第 i i i 个房间内恰好有 r i r_i ri​ 头牛。

为了让奶牛们有序的进入牛棚，他计划打开一个外门，让牛从该门进入。

然后，每头牛顺时针(即当 i < n i<n i<n 时，第 i i i 个房间只能走到第 i + 1 i+1 i+1 个房间；当 i = n i=n i=n 时，第 i i i 个房间只能走到第 1 1 1 个房间)穿过房间，直到到达合适的房间为止。

约翰希望通过合理选择打开的门，使得所有奶牛的行走距离之和尽可能小（这里只考虑每头牛进入牛棚以后的行走距离）。

请确定他的奶牛需要行走的最小总距离。

输入格式
第一行包含整数 n n n。

接下来 n n n 行，包含 r 1 , … , r n r_1,…,r_n r1​,…,rn​。

输出格式
输出所有奶牛需要行走的最小总距离。

数据范围
3 ≤ n ≤ 1000 , 1 ≤ r i ≤ 100 3≤n≤1000, 1≤r_i≤100 3≤n≤1000,1≤ri​≤100

输入样例：

5
4
7
8
6
4

输出样例：

48

样例解释
最佳方案是让奶牛们从第二个房间进入。

#include<iostream>using namespace std;const int N = 1010, INF = 1e9;int r[N];int main(){int n;cin >> n;for(int i = 0; i < n; i++) cin >> r[i];int res = INF, sum;for(int i = 0; i < n; i++){sum = 0;for(int j = 1; j < n; j++) sum += j * r[(i + j) % n];res = min(res, sum);}cout << res << endl;return 0;
}