[USACO1.1]贪婪的送礼者Greedy Gift Givers 题目解析

题目描述

对于一群

个要互送礼物的朋友，GY 要确定每个人送出的钱比收到的多多少。在这一个问题中，每个人都准备了一些钱来送礼物，而这些钱将会被平均分给那些将收到他的礼物的人。

然而，在任何一群朋友中，有些人将送出较多的礼物(可能是因为有较多的朋友)，有些人有准备了较多的钱。

给出一群朋友，没有人的名字会长于

字符，给出每个人将花在送礼上的钱，和将收到他的礼物的人的列表，请确定每个人收到的比送出的钱多的数目。

输入格式

第一行一个正整数

，表示人数。接下来

行，每行一个字符串表示人名。

接下来有

段内容，对于每一段：第一行是将会送出礼物人的名字。

第二行包含二个非负整数，第一个是原有的钱的数目 (

)，第二个

是将收到这个人礼物的人的个数 如果

, 在下面

行列出礼物的接受者的名字，一个名字一行。

输出格式

输出共

行，每行输出一个人的名字和该人收到的钱比送出的钱多的数目。名字的顺序应该与输入第

行至

行的顺序相同。

送出的钱永远是整数，即假设送礼人一次向

人送出

元，每个人应该得到 $ \lfloor n/m \rfloor $ 元。剩余未送出的钱应返还给送礼者。

样例 #1

样例输入 #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提示

【数据范围】

题目翻译来自NOCOW。

USACO Training Section 1.1

解析：

这个问题可以通过模拟赠送礼物的过程来解决。主要任务是跟踪每个人送出和收到的钱，并根据这些计算出每个人的净变化（收到的钱减去送出的钱）。解决这个问题的步骤如下：

解决思路：

1、输入数据解析：

• 首先读取人数n和接下来n个朋友的名字。

• 接着对于每个朋友，读取其赠送礼物的详细信息，包括准备的金额和接受者人数。

2、数据结构设计：

• 使用一个结构体来存储每个人的信息，包含人的名字、收到的钱数、送出的钱数。

3、模拟送礼物过程：

• 对于每个送礼者，读取他们准备赠送的金额和接受者人数，赠送的金额注意不能整除的情况。如果接受者人数不为

，则计算每个接受者应获得的金额（整数除法）。

4、输出结果：

• 按照最初输入的顺序输出每个人的名字和他们收到的比送出的钱多的数目。

下面是代码：

#include<bits/stdc++.h>

using namespace std;

struct Person{

string name;

int song,shou;

}p[15];

int n;

int main() {

cin>>n;

for(int i=1;i<=n;i++) {

cin>>p[i].name;

}

for(int i=1;i<=n;i++) {

string s;int money,num;

cin>>s;cin>>money>>num;

for(int j=1;j<=n;j++) {

if(s==p[j].name && num!=0) {

p[j].song = money-money%num;  //计算送出的钱

break;

}

}

for(int j=1;j<=num;j++) {

cin>>s;

for(int k=1;k<=n;k++) {

if(s==p[k].name && num!=0) {

p[k].shou += money / num; //计算收到的钱

}

}

}

}

for(int i=1;i<=n;i++) {  //输出

cout<<p[i].name<<" "<<p[i].shou-p[i].song<<endl;  //收到的钱减去送出的钱

}

return 0;

}复杂度分析：

该算法的时间复杂度为

，因为最多有

个朋友，每个人可能送礼给最多

个朋友。在题目的限制范围非常小

。这个题目的关键在于正确处理输入数据并跟踪每个人送出和收到的钱的变化。