欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

贪心算法-环形均分纸牌问题(均等笔题解)

程序员文章站 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;
}

参考资料: