【洛谷】P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers（模拟）题解

题解"/>

【洛谷】P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers（模拟）题解

原题地址：

题目描述

对于一群（NP个）要互送礼物的朋友，GY要确定每个人送出的钱比收到的多多少。在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。给出一群朋友，没有人的名字会长于 14 字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。

输入输出格式

输入格式：

第 1 行: 人数NP,2<= NP<=10

第 2 行 到 第NP+1 行:这NP个在组里人的名字一个名字一行

第NP＋2到最后：

这里的I段内容是这样组织的：

第一行是将会送出礼物人的名字。

第二行包含二个数字:第一个是原有的钱的数目（在0到2000的范围里），第二个 NGi 是将收到这个人礼物的人的个数 如果 NGi 是非零的, 在下面 NGi 行列出礼物的接受者的名字，一个名字一行。

输出格式：

输出共 NP 行，每行输出一个人的名字和该人收到的钱比送出的钱多的数目。名字的顺序应该与输入第 2 行至 NP+1 行的顺序相同。

送出的钱永远是整数，即假设送礼人一次向 m 人送出 n 元，每个人应该得到 ⌊n/m⌋ 元。剩余未送出的钱应返还给送礼者。

输入输出样例

输入样例#1：

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

输出样例#1：

dave 302
laura 66
owen -359
vick 141
amr -150


说明

时空限制：1000ms,128M

题目翻译来自NOCOW。

USACO Training Section 1.1

思路：模拟题。

1. 送钱的人送出的钱平均分成m份，遍历所有人，找到收钱的那个人，总钱数加上收到的钱数，然后送钱的人总钱数减去实际送出的钱数，这里要注意一点，实际送出的钱数是指平均每份的钱乘以m份。
2. 还有一个要注意的点就是strcmp函数只能比较char型的字符串，不可以比较string型的。具体见代码注释。
   
   

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct node{char name[15];	//定义人名 int moneysum;	//定义每个人的总钱数 
}arr[15];
int main(){ios::sync_with_stdio(0);	//取消同步 int np;cin>>np;	//np个人 for(int i=1;i<=np;i++)	//输入np个人的名字 cin>>arr[i].name;int t,n,m;	//n表示送出的钱数，m表示收钱的人数 char str1[15];	//str1表示不能定义为char型，因为strcmp只能比较char型的字符串  for(int i=1;i<=np;i++){cin>>str1;	//输入送礼物的人名 for(int j=1;j<=np;j++){	//遍历所有人查找该人的序号 if(!strcmp(str1,arr[j].name)){	//如果找到该人 t=j;	//t暂存该人的序号 break;	//后面的不用找了 }}cin>>n>>m;	 int money_in,money_out;	//分别表示收到的钱数和送出的钱数 if(n||m){	//如果钱数和人数均不为0 money_in=n/m;	//记录平均每人收到的钱数 money_out=money_in*m;	//记录实际送出的钱数，剩下的不算进去 }else if(!n||!m)	//如果n或者m等于0，则可以直接跳过了 continue;arr[t].moneysum-=money_out;	//送钱的人减掉实际送出的钱数 char str2[15];	//str2表示收钱的人名 for(int k=1;k<=m;k++){	//共有m个人收到钱 cin>>str2;for(int h=1;h<=np;h++){	//遍历np个人，查找该人 if(!strcmp(str2,arr[h].name)){	//如果找到了该人 arr[h].moneysum+=money_in;	//他的总钱数加上收入的钱数 break;	//后面的不用找了 }}}}for(int i=1;i<=np;i++)	//最后遍历np个人，输出全部人名和最后的钱数 cout<<arr[i].name<<' '<<arr[i].moneysum<<endl;return 0;
}