3099: CT5圆环选址
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
给定一个长度为 �n 的环状数列 �1,�2,⋯,��a1,a2,⋯,an，所谓环状，是指在考虑相邻关系时，需要把 �1a1 和 ��an 也看做是一对邻居。
数列的每个位置上都有一堆物资，数列上的每个数字表示该堆物资的数量。我们希望从 �n 个位置中挑选一个位置，使得所有物资能聚集到一起，而且运费总和达到最小。
物资只能沿着相邻位置搬运，每当一个单位物资的移动一个单位距离时，需要支付一个单位的运费。请问如何选择一个聚集点，使得运费总和达到最小？
输入
第一行：单个整数表示 �n。
第二行：�n 个整数表示 �1,�2,⋯,��a1,a2,⋯,an。
第二行：�n 个整数表示 �1,�2,⋯,��a1,a2,⋯,an。
- 对于 30%30% 的数据，1≤�≤1001≤n≤100；
- 对于 60%60% 的数据，1≤�≤20001≤n≤2000；
- 对于 100%100% 的数据，1≤�≤500,0001≤n≤500,000，
- 0≤��≤1,000,0000≤ai≤1,000,000。
输出
单个整数：表示将所有物资移动到一起的最小总运费。
样例输入 复制
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
提示：
1. 公式推导
2. 总结通项式
3.善用指针变量
选择5作为聚集点，运费计算公式为1*1+2*2+3*2+4*1=15
提示：
1. 公式推导
2. 总结通项式
3.善用指针变量