题目
问题描述
有若干个朋友，朋友之间可以选择互相赠送一些有价值的礼物。一个人可以选择将一部分钱分给若干个朋友，例如某人送给其他两个人钱，总共赠送3元，两个人平均分，原本应该是每人1.5元，但是只能取整数，所以这两个人每人能够得到1元，所以他总共送出去2元，自己剩下1元。
现在，我们知道有NP个人，将NP个人的名字告诉我们，随后给出一个人的名字代表他将进行捐赠，下一行有两个数字，代表这个人的初始的金额X，和要将X元平分给Y个人，下面Y行分别是接受捐赠的人的名字。
最后需要我们计算出，每个人最终的金额与初始金额的差，可能会有负数出现。
数据范围
- 名字不会超过14个字符
2 <= NP <= 100 <= X <= 2000
样例输入
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0
样例输出
dave 302
laura 66
owen -359
vick 141
amr -150
解题思路
定义一个Person结构体，将姓名、初始金额，和实时金额作为属性保存。之后开始模拟操作即可，在进行除法时请注意避免除数为0的情况。
解题代码
/*
ID: yinzong2
PROG: gift1
LANG: C++11
*/
#define MARK
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 20;
int num;
struct Person {
char name[maxn];
int iniMoney;
int money;
} p[maxn];
int main() {
#ifdef MARK
freopen("gift1.in", "r", stdin);
freopen("gift1.out", "w", stdout);
#endif
while(~scanf("%d", &num)) {
for(int i = 0; i < num; i++) {
scanf("%s", p[i].name);
p[i].iniMoney = p[i].money = 0;
}
char str1[maxn], str2[maxn];
int ini, cnt;
for(int i = 0; i < num; i++) {
scanf("%s", str1);
scanf("%d%d", &ini, &cnt);
for(int j = 0; j < num; j++) {
if(strcmp(str1, p[j].name) == 0) {
p[j].iniMoney = ini;
p[j].money += ini;
if(cnt != 0)p[j].money -= (ini/cnt)*cnt;
break;
}
}
for(int j = 0; j < cnt; j++) {
scanf("%s", str2);
for(int k = 0; k < num; k++) {
if(strcmp(str2, p[k].name) == 0) {
if(cnt != 0)p[k].money += (ini/cnt);
break;
}
}
}
}
for(int i = 0; i < num; i++) {
printf("%s %d\n", p[i].name, p[i].money-p[i].iniMoney);
}
}
return 0;
}
代码优化
在上一个代码中，每次出现一个人名我必须用循环O(N)的复杂度来查找，确定这个人名是谁之后才能进行操作。现在我用一个map来保存Person的信息，其中名字作为查找的key，对应这个人出现的次序作为value。在代码中我用了一个Person数组p来存储这些人的信息，现在这样用map处理之后，每次得到一个人名，我都能利用p[ map[name] ]这种语句来得到这个人，map查找的时间复杂度为O(logN)，如果数据量很大的话这种优化还是挺有效率的。
解题代码(Type 2)
/*
ID: yinzong2
PROG: gift1
LANG: C++11
*/
#define MARK
#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int maxn = 20;
struct Person {
string name;
int iniMoney;
int money;
}p[maxn];
map<string, int> mp;
int np;
int main() {
#ifdef MARK
freopen("gift1.in", "r", stdin);
freopen("gift1.out", "w", stdout);
#endif
while(~scanf("%d", &np)) {
string str;
for(int i = 0; i < np; i++) {
cin >> str;
p[i].name = str;
p[i].iniMoney = p[i].money = 0;
mp[str] = i;
}
int ini, cnt;
for(int i = 0; i < np; i++) {
cin >> str;
scanf("%d%d", &ini, &cnt);
int id = mp[str];
p[id].iniMoney = ini;
p[id].money += ini;
if(cnt != 0) {
p[id].money -= (ini/cnt)*cnt;
}
for(int j = 0; j < cnt; j++) {
cin >> str;
int id2 = mp[str];
if(cnt != 0) {
p[id2].money += (ini/cnt);
}
}
}
for(int i = 0; i < np; i++) {
cout << p[i].name << " " << (p[i].money-p[i].iniMoney) << endl;
}
}
return 0;
}