1843.圆形牛棚

1843. 圆形牛棚

题目描述：

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

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

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

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

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

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

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

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

输入格式

第一行包含整数 $ n $ 。

接下来 $ n $ 行，包含 $ r_1,…,r_n $ 。

输出格式

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

数据范围

$$3\le n\le 1000\\ 1\le ri \le 100$$

输入样例：

5
4
7
8
6
4

输出样例：

48

样例解释

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

题解：

当从第一个房间进入时，

$$ans_1 = 0\times r_1 + 1\times r_2 + \dots + (n - 1) \times r_n$$

当从第二个房间进入时，

$$ans_2 = (n - 1) \times r_1 + 0 \times r_2 + \cdots + (n - 2) \times r_n$$

注意观察，发现

$$ans_2 = ans1 - sum + n \times r_1\\ sum = \sum_{i=1}^{n} r_i$$

因此只需要求解一个 $ ans_1 $ 和 $ sum $ 就行了，后面的全部递推出来。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tcase;

    cin >> n;
    int minx = INF;
    int ans = 0;
    int sum = 0;
    // ans1 = 0*x1 + 1*x2 +...+(n-1)*xn
    // ans2 = (n-1)x1 + 0*x2 + 1*x3 + ... + (n-2)*xn
    // delt = -nx1 + sum
    // ans2 = ans1 + nx1 - sum
    // ans - sum + n * x1
    for (int i = 1, x; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
        ans += (i - 1) * a[i];
    }
    minx = min(minx, ans);
    for (int i = 2; i <= n; i++)
    {
        ans = ans - sum + n * a[i - 1];
        minx = min(ans, minx);
    }
    cout << minx << endl;
    return 0;
}