多数据制衡问题的解决方案

c/c++

浏览数:156

2019-3-30

AD:资源代下载服务

【问题】
假设存在这样一个问题,有n(n<=10^5)个人打算合伙开店,每个人都为店铺贡献了一部分钱,后来这家店打算以互相转钱的方式让每个人出资相同,以方便均摊利润。请给出转钱方案,即谁应该向谁转多少钱,方案要求尽量简洁。(注:金钱数额小数点后不超过两位)

【题解】

个人成本分布示例图.png

(1)如图所示,题目的意思是低于均值的人要将钱转给高于均值的人,使得在总资本不变的情况下平均分配资本,使得每个人出资相同。
(2)对于每一个出资低于均值的人来说,需要遍历其他人的出资,只要有人的出资高于均值且没被消减完全,则对其进行消减,结束后自己的出资增加相应数额。直到最后所有人的出资均为均值即可。
(3)应当引入一个极小数字1e-8进行对浮点数的比较判断,详见代码。

以下是C/C++的参考代码:

#include<cstdio>
#include<cmath>
const double eps = 1e-8;
#define Less(a,b) (((a)-(b))<(-eps))
#define More(a,b) (((a)-(b))>(eps))
#define Equ(a,b) ((fabs((a)-(b)))<(eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
struct Invest {
    char name[10];
    double money, More, Less;//分别代表投资金额、超出均值金额、低于均值金额
} I[100010];
int main() {
    int n;
    double sum = 0.0;
    printf("请输入投资人数:");
    scanf("%d", &n);
    printf("请按人数输入投资人的姓名和投资数额:\n");
    for(int i = 0; i < n; i++) {
        scanf("%s %lf", I[i].name, &I[i].money);
        sum += I[i].money;
    }
    double ave = sum / (n * 1.0);
    for(int i = 0; i < n; i++) {
        if(Less(I[i].money, ave)) {
            I[i].Less = ave - I[i].money;
            I[i].More = 0.0;
        }
        if(More(I[i].money, ave)) {
            I[i].Less = 0.0;
            I[i].More = I[i].money - ave;
        }
        if(Equ(I[i].money, ave)) {
            I[i].Less = 0.0;
            I[i].More = 0.0;
        }
    }
    printf("----------------------------------\n");
    printf("转钱方案为:\n");
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(I[i].More == 0.0 && I[i].Less == 0.0) count++;
    }
    if(count == n) printf("无需转钱");
    for(int i = 0; i < n; i++) {
        if(I[i].Less == 0.0) continue;
        for(int j = 0; j < n; j++) {
            if(j == i || I[j].More == 0.0) continue;
            if(MoreEqu(I[j].More, I[i].Less)) {
                I[j].More -= I[i].Less;
                if(I[i].Less != 0.0) printf("%s需要支付给%s共%0.2f元\n", I[i].name, I[j].name, I[i].Less);
                I[i].Less = 0.0;
            }
            else {
                I[i].Less -= I[j].More;
                if(I[i].Less != 0.0) printf("%s需要支付给%s共%0.2f元\n", I[i].name, I[j].name, I[j].More);
                I[j].More = 0.0;
            }
        }
    }
    return 0;
}

下面给出三组数据的测试结果:

数据相同时.png
一人不用转时.png
复杂数据时.png

该题类似于贪心算法的求解模式,
但还没有考虑算法的效率问题以及方案是否是最优,
欢迎在留言区提供你的想法,
敬请关注后续更新及代码详解。。。