UVa 538 Balancing Bank Accounts

题目描述

题目要求根据给定的交易记录，计算每个人的净收支，然后输出一组新的交易，使得所有人的账户归零。输出的交易数最多为n−1n-1n−1条。金额必须为非负整数。

输入格式

每个测试用例第一行包含两个整数nnn（2≤n≤202 \le n \le 202≤n≤20）和ttt（1≤t≤10001 \le t \le 10001≤t≤1000）。接下来nnn行每行一个人名。然后ttt行，每行格式name1 name2 amount，表示name1name1name1支付amountamountamount给name2name2name2。输入以0 0结束。

输出格式

对于每个测试用例，输出Case #i，然后输出若干行交易（格式同输入），每条交易金额非负。每个测试用例输出后跟一个空行。

样例

输入

2 1 Donald Dagobert Donald Dagobert 15 4 4 John Mary Cindy Arnold John Mary 100 0 0

输出

Case #1 Dagobert Donald 15 Case #2 Mary John 140 Cindy John 10 Arnold John 150

题目分析

本题的核心是计算每个人的净余额，然后通过n−1n-1n−1条交易将所有余额归零。

净余额计算

对于每笔交易A B amount，表示AAA支付给BBBamountamountamount。因此：

• AAA的余额减少amountamountamount。
• BBB的余额增加amountamountamount。

最终，所有余额之和应为000。

平衡策略

将所有人中净余额为正者视为“债主”，净余额为负者视为“债务人”。为了用n−1n-1n−1条交易完成平衡，可以选取一个人作为“中间人”，例如最后一个人。其他所有人的净余额直接与中间人进行结算：

• 若某人净余额为正，则中间人支付给该人。
• 若某人净余额为负，则该人支付给中间人。

这样总共最多n−1n-1n−1条交易。

复杂度分析

O(n+t)O(n + t)O(n+t)。

代码实现

// Balancing Bank Accounts// UVa ID: 538// Verdict: Accepted// Submission Date: 2016-12-21// UVa Run Time: 0.030s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,t,cases=0,amount;string name1,name2;while(cin>>n>>t,n>0){map<string,int>money;string names[30];for(inti=1;i<=n;i++){cin>>names[i];money[names[i]]=0;}for(inti=1;i<=t;i++){cin>>name1>>name2>>amount;money[name1]-=amount;money[name2]+=amount;}cout<<"Case #"<<++cases<<'\n';for(inti=1;i<n;i++){if(money[names[i]]>0)cout<<names[i]<<' '<<names[n]<<' '<<money[names[i]]<<'\n';if(money[names[i]]<0)cout<<names[n]<<' '<<names[i]<<' '<<abs(money[names[i]])<<'\n';}cout<<'\n';}return0;}