UVA 538 - Balancing Bank Accounts
題目鏈接
題意:給定一些人的欠錢關系,要求在n-1次內還清錢,問方案
思路:貪心,處理出每一個人最后錢的狀態,然后直接每一個人都和最后一個人操作就可以
代碼:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <map>
using namespace std;
const int N = 25;
int n, m, have[N];
map<string, int> hash;
string name[N];
int main() {
int cas = 0;
while (~scanf("%d%d", &n, &m) && n || m) {
hash.clear();
memset(have, 0, sizeof(have));
for (int i = 1; i <= n; i++) {
cin >> name[i];
hash[name[i]] = i;
}
string a, b; int val;
while (m--) {
cin >> a >> b >> val;
int u = hash[a], v = hash[b];
have[u] += val;
have[v] -= val;
}
printf("Case #%d\n", ++cas);
for (int i = 1; i < n; i++) {
if (have[i] < 0)
cout << name[i] << " " << name[n] << " " << -have[i] << endl;
else if (have[i] > 0)
cout << name[n] << " " << name[i] << " " << have[i] << endl;
have[n] -= have[i];
}
printf("\n");
}
return 0;
}