圆形牛棚

Original Link

思路：

• 前缀和。
  • 由于牛棚为环状，故将数组首尾相连。
  • 利用 sum 记录牛牛们需要走的距离，前缀和记录 a[i] 到 i ~ n 的距离。
  • 从连接后的数组开始，即 i 从 n 到 2 * n 遍历，sum 减去后一个房间牛牛走过的距离，再加上该房间牛牛走到 i + n 的距离。
  • 维护一个最小的 ans = min(ans, sum) 即可。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e6 + 3;

int a[N];

void solve(){
    int n; cin >> n;
    LL sum = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i]; a[i + n] = a[i];
        sum += a[i] * (i - 1);
    }
    for(int i = 1; i <= 2 * n; i ++) a[i] += a[i - 1];
    LL ans = 0x3f3f3f3f;
    for(int i = n + 1; i <= 2 * n; i ++){
        sum = sum + n * (a[i] - a[i - 1]) - (a[i] - a[i - n]);
        ans = min(ans, sum);
    }
    cout << ans << endl;
}

int main(){
    solve();
    return 0;
}