贪心算法-环形均分纸牌问题(均等笔题解)
程序员文章站
2022-06-22 09:26:04
解题思路 首先,假设每个人向左边传递 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](其中 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; }
参考资料:
下一篇: 感冒吃什么好得快,推荐几种感冒的食疗方法