1.1 普及组

1.1.1　互送礼物

【例题讲解】互送礼物（gift）USACO 1.1.2 Greedy Gift Givers

每个人都准备了一些钱用于给他的朋友们送礼物，他们把准备的钱平分后购买礼物给各自的朋友们，所有人送礼物的钱都是整数，而且尽可能多准备，没能花出的钱由送礼物者自己保留。

请你统计每个人因此而产生的最终盈亏数。

【输入格式】

第1行为一个整数n（2≤n≤10），表示总人数。 

随后用n行描述每个人的名字，假设没有人的名字会长于14个字符。

随后描述每个人送礼物的情况：每个人对应的第1行是他的名字，第2行有两个数字，第1个数字为他准备的钱的金额（范围为0～2000），第2个数字是他要送礼物的朋友数m，随后m行为他要送礼物的朋友的名字。

【输出格式】

输出n行，即按输入顺序输出每个人的名字和他因互送礼物而产生的盈亏数，名字与数字之间以空格间隔。

【输入样例】

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

【算法分析】

按题目的要求模拟计算即可。保存每个人的名字和钱的金额可以使用结构体或者标准模板库(Standard Template Library,STL)里的map。计算时注意除数为0时的处理。

参考代码如下。

 1  //互送礼物
 2  #include <bits/stdc++.h>
 3  using namespace std;
 4  
 5  map<string,int>ans;                               //使用map，名字为数组下标（索引）
 6  
 7  int main()
 8  {
 9    int n,money;
 10    cin>>n;
 11    string name[15],s,Friend;                   //friend为关键字，故Friend 中的F大写
 12    for(int i=1; i<=n; i++)
 13      cin>>name[i];
 14    for(int i=1,num; i<=n; i++)
 15    {
 16      cin>>s>>money>>num;
 17      for(int j=1; j<=num; j++) 
 18      {
 19        cin>>Friend;    
 20        ans[Friend]+=money/num;                     //该朋友收到的礼物对应的钱的金额
 21      }
 22      if(num!=0)                                    //必须先确保除数不为0
 23        ans[s]=ans[s]-money+money%num;              //计算本人盈亏数 
 24    }
 25    for(int i=1; i<=n; i++)
 26      cout<<name[i]<<' '<<ans[name[i]]<<endl;
 27    return 0;
 28  }