（算法）AA制

题目：

A、B、C、D四个人去吃大餐，吃饭去说好，付钱时AA制，但最后结账时，因为4个人带的钱不一样多，最后A付了112元，B付了86元，C付了10元，D没带钱，所以没有付；

但AA制需要平摊餐费，所以需要设计一种方案来解决这个问题。

现假设有n个人，m个人付款，请通过编程来解决这个问题（解决问题有多种方案，只需实现一种即可）

思路：

1、计算每个人本需要支付的钱，即平均数；

2、计算实际上每个人的盈亏，即支付金额减去平均数；

3、通过盈亏关系进行分配，即少付的将钱支付给多付的；

以题目为例，平均数为52，减去平均数后的盈亏关系为：

A：+60

B：+34

C：-42

D：-52

那么此时C、D需将钱支付给A和B，怎么支付呢？可以将问题转化为一下的矩阵形式：

	A	B
C
D

矩阵每个格子表示：x应该支付多少给y，从上到下依次填写表格，可以得到：

	A	B
C	42	0
D	18	34

代码：

#include<iostream>

#include<vector>

using namespace std;

const float EPSINON=0.00001;

bool isZero(float x){

    return (x>=-EPSINON) && (x<=EPSINON);

}

int main(){

    int num_all;

    int num_paid;

    int num_unpaid;

    float sum,avg;

    int idx;

    float money;

    cout<< "Input number of people and number of who have paid: " <<endl;    

    while(cin >> num_all >> num_paid){

        vector<float> all(num_all,0.0);

        sum=;

        for(int i=;i<num_paid;i++){

            cin>>idx>>money;

            all[idx-]=money;

            sum+=all[idx-];

        }

        cout<<endl;

        avg=sum/num_all;

        vector<int> receive;

        vector<int> pay;

        for(int i=;i<num_all;i++){

            all[i]-=avg;

            if(all[i]<)

                pay.push_back(i+);

            if(all[i]>)

                receive.push_back(i+);

        }

        int row=pay.size();

        int col=receive.size();

        vector<vector<float> > table(row,vector<float>(col,0.0));

        float from,to;

        for(int i=;i<row;i++){

            for(int j=;j<col;j++){

                from=pay[i]-;

                to=receive[j]-;

                if(isZero(all[from]))

                    break;

                if(isZero(all[to]))

                    continue;

                if(all[from]+all[to]>=){

                    table[i][j]=-all[from];

                    all[to]=all[from]+all[to];

                    all[from]=0.0;

                }

                else{

                    table[i][j]=all[to];

                    all[from]=all[from]+all[to];

                    all[to]=0.0;

                }

            }

        }

        for(int i=;i<row;i++){

            for(int j=;j<col;j++){

                cout<< table[i][j]<<" ";

            }

            cout<<endl;

        }

        cout<<endl;

        for(int i=;i<row;i++){

            for(int j=;j<col;j++){

                if(!isZero(table[i][j]))

                    cout<<pay[i]<<" paid "<<receive[j]<<" "<<table[i][j]<<endl;

            }

        }

    }

    return ;

}

巴特西

（算法）AA制

题目：

思路：

代码：

最新文章

热门文章