【USACO】【Section1.1】Greedy Gift Givers

时间:2021-04-13 14:40:45

小白题,也没啥好说的。关键我的算法感觉特别菜的一点是每次要遍历数组从人名找对应的编号,这个效率就很低了。看了ANALYZE里面也是这样的。不过它比我好的一点是我多余设置了initial_money变量,确实是不需要的。还有一点就是有可能接受礼物的人是0个,要判断。如果是0就不用60~67行了,而且60行的分母也会为0;

 1 /*ID:Moment1991
 2 PROG:gift1
 3 LANG:C++
 4    Test 1: TEST OK [0.000 secs, 3504 KB]
 5    Test 2: TEST OK [0.000 secs, 3504 KB]
 6    Test 3: TEST OK [0.000 secs, 3504 KB]
 7    Test 4: TEST OK [0.000 secs, 3504 KB]
 8    Test 5: TEST OK [0.000 secs, 3504 KB]
 9    Test 6: TEST OK [0.000 secs, 3504 KB]
10    Test 7: TEST OK [0.000 secs, 3504 KB]
11    Test 8: TEST OK [0.000 secs, 3504 KB]
12    Test 9: TEST OK [0.000 secs, 3504 KB]
13 
14 */
15 #include <iostream>
16 #include <fstream>
17 #include <string.h>
18 using namespace std;
19 typedef struct PERSON{
20         char name[15];
21         int intial_money;
22         int final_money;
23     }P;
24 P p[10];
25 int np;
26 int find_pos(char person[])
27 {
28     for(int i =0;i < np;i++)
29     {
30         //cout << person<<endl;
31         if(strcmp(person,p[i].name) == 0)
32             return i;
33     }
34     return -1;
35 }
36 int main()
37 {
38     ifstream cin("gift1.in");
39     ofstream cout("gift1.out");
40 
41     cin >> np;
42     for(int i = 0;i <np;i ++)
43     {
44         cin >> p[i].name;
45     }
46     for(int i = 0;i < np;i++)
47     {
48         char giver[15];
49         int giver_money,receivers_num,each_money,giver_pos,receivers_pos;
50         char receiver[15];
51 
52         cin >> giver;
53 
54         giver_pos = find_pos(giver);
55 
56         cin >> p[giver_pos].intial_money;
57         cin >> receivers_num;
58 
59         if(receivers_num != 0){
60             each_money = p[giver_pos].intial_money / receivers_num;
61             p[giver_pos].final_money -= each_money * receivers_num;
62 
63             for(int j = 0;j < receivers_num;j++)
64             {
65                 cin >> receiver;
66                 receivers_pos = find_pos(receiver);
67                 p[receivers_pos].final_money += each_money;
68             }
69         }
70     }
71     for(int i = 0;i <np;i ++)
72         cout << p[i].name <<" "<<p[i].final_money<<endl;
73 }