本文最后更新于 565 天前,其中的信息可能已经有所发展或是发生改变。
思想:
- 前缀和。
- 由于牛棚为环状,故将数组首尾相连。
- 利用
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;
}