圆形牛棚
问题描述
作为当代建筑的爱好者，农夫约翰建造了一个完美圆环形状的新牛棚。
牛棚内部有 n 个房间，围成一个环形，按顺时针编号为 1∼n。
每个房间都既有通向相邻两个房间的门，也有通向牛棚外部的门。
约翰想让第 i 个房间内恰好有 ri 头牛。
为了让奶牛们有序的进入牛棚，他计划打开一个外门，让牛从该门进入。
然后，每头牛顺时针穿过房间，直到到达合适的房间为止。
约翰希望通过合理选择打开的门，使得所有奶牛的行走距离之和尽可能小（这里只考虑每头牛进入牛棚以后的行走距离）。
请确定他的奶牛需要行走的最小总距离。
输入格式
第一行包含整数 n。
接下来 n 行，包含 r1,…,rn。
输出格式
输出所有奶牛需要行走的最小总距离。
数据范围
3≤n≤1000,
1≤ri≤100
输入样例：
5
4
7
8
6
4
输出样例：
48
样例解释
最佳方案是让奶牛们从第二个房间进入。
思路分析
方法一：
完整代码
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1010;
int a[N];
#define INF 1e18;
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
int res = INF;
for(int i = 0; i < n; i++)
{
int temp = 0;
for(int j = 1; j < n; j++)
{
temp += a[(i + j) % n] * j;
}
res = min(res, temp);
}
cout << res << endl;
return 0;
}
方法二：前缀和的和
完整代码
include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1010;
int a[N], r[N];
int sum(int i)
{
int res = 0;
int u = i - 1;
for(int j = n; j > 0; j--)
{
a[n - j] = r[(j + u) % n];
}
for(int j = 0; j < n; j++)
{
a[j] += a[j - 1];
}
for(int j = 0; j < n - 1; j++)
{
res += a[j];
}
return res;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
scanf("%d", &r[i]);
}
int ans = 1e18;
for(int i = 0; i < n; i ++)
{
ans = min(ans, sum(i));
}
cout << ans << endl;
return 0;
}