题目描述
给定一个长度为n的环状数列a1,a2,……，an,所谓环状，是指在考虑相邻关系时，需要把a1和an也看做是一对邻居。
每个数字各自表示一堆物资的数量。我们希望从n个位置中挑选一个位置，使得所有物资能聚集到一起，而且运费总和达到最小。
物资只能沿着相邻位置搬运，每当一单位物资移动一单位距离时，需要花费一单位运费。请问如何选择一个聚集点，使得运费总和达到最小？
输入格式
第一行：单个整数表示 n。
第二行：n 个整数表示a1,a2,……,an
输出格式
单个整数：表示将所有物资移动到一起的最小总运费。
数据范围
1<=n<=500000
0<=ai<=1000000
空间限制：256MB
时间限制：1000ms
样例数据
输入:
5
1 2 3 4 5
输出:
14
说明:
选择4作为聚集点，运费计算公式为1*2+2*2+3*1+5*1=14
选择5作为聚集点，运费计算公式为1*1+2*2+3*2+4*1=15
2 条评论
-
Vijos永远NB (郑灏轩) LV 10 @ 2022-01-13 18:55:48
P几几
-
@ 2022-01-03 12:41:28
我已经得了60分，剩下超时了：
#include <iostream>
using namespace std;
int a[1000000] ;
int main(){
int n ;
cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
}
long min_cost = 999999999999;
for(int j = 0; j < n; j++){
long cost = 0;
for(int i = 0; i < n; i++){
long pj = min((i-j+n)%n, (j - i +n )%n );
// printf("%ld ",pj );
cost += pj * a[i];
}
min_cost = min(min_cost, cost);
// printf("\n");
}
cout << min_cost;
return 0;
}
- 1
