解题思路
首先,假设每个人向左边传递 c[i](其中 c[1] 表示第一个人向最后一个人传递的值),则 c[i] 的绝对值之和为传递的最小次数。
假设每个人的初始值为 a[i] ,最终值为 ave(sum/n) ,则 ave=a[i]-c[i]+c[i+1] 。
处理 a[i]=a[i]-ave ,上式变为 c[i+1]=c[i]-a[i] 。
于是 求 c[i] 的绝对值之和最小值 问题转化成了:(货仓选址问题)给定数轴上的n个点,找出一个到它们的距离之和尽量小的点,这个点就是这些数的中位数。
解题步骤
1.a[i]=a[i]-ave,c[i+1]=c[i]-a[i]
2.对 c[i] 排序,取中位数
实例题解
均等笔
题目描述
n 个人围成一圈,每人有 ai 支笔。每人可以向左右相邻的人传递笔,每人每次传递一支笔消耗的能量为 1。
求使所有人获得均等数量的笔的最小能量。输入格式
第一行一个整数 n ,表示人的个数(30%的数据,n<=1000;100%的数据,n<=1e6)。
接下来 n 行,每行一个整数 ai 。输出格式
输出一个整数,表示使所有人获得均等笔的最小能量。(答案保证可以用64位有符号整数存储)
完整代码
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int a[1000010], c[1000010];
int main()
{
int n, i;
long long ans = 0, ave = 0;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
ave += a[i];
}
ave /= n;
for (i = 0; i < n; i++) {
a[i] -= ave;
}
for (i = 1; i <= n; i++) {
c[i] = c[i - 1] - a[i - 1];
}
sort(c + 1, c + 1 + n);
for (i = 1; i <= n; i++) {
ans += abs(c[i] - c[n / 2]);
}
printf("%lld", ans);
return 0;
}
参考资料:糖果传递(中位数、环形均分纸牌)
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!