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  }