圆形牛棚

问题描述

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

牛棚内部有 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;

}