大专网站建设论文,海口网站建设呢,用友erp管理软件系统,网站网页设计的组成有 n个小朋友坐成一圈#xff0c;每人有 a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n#xff0c;表示小朋友的个数。
接下来 n 行#xff0c;每行一个整数 a[i]每人有 a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n表示小朋友的个数。
接下来 n 行每行一个整数 a[i]表示第 i个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数表示最小代价。
数据范围
1≤n≤1000000 0≤a[i]≤2×109 数据保证一定有解。
输入样例
4
1
2
5
4输出样例
4 题意
ai向ai1传递xi个通过xi可正可负求abs(x1)abs(x2)...abs(xn)的最小值
分析
一大堆数学证明我证不过来所以直接给结论吧。
要求
|x1||x2|...|xn|最小值
即求
|xn-b-a1||xn-2b-a1-a2||xn-nb-a1-a2-...-an|
将该问题转换为
货仓选址问题即可
#include iostream
#include algorithmusing namespace std;
typedef long long ll;
const int N1e610;
ll a[N],b,c[N];
int main(){int n;cinn;for(int i1;in;i){cina[i];ba[i];a[i]a[i-1];}b/n;for(int i1;in;i){c[i]i*b-a[i];}sort(c1,cn1);ll dc[n/21];ll res0;for(int i1;in;i){resabs(c[i]-d);}coutres;return 0;
}
