USACO1.1.2 - Greedy Gift Givers
【摘要】
贪婪礼品送货员
一组NP（2≤NP≤10）唯一命名的朋友决定交换礼物的钱。这些朋友中的每一个可能或可能不会给任何或所有其他朋友一些钱。同样，每个朋友可能或可能不从任何或所有其他朋友接收钱。你在这个问题上的目标是推断每个人给予的收入多少。
赠送礼物的规则可能与您的期望不同。每个人都留出一定数量的钱来给予这笔钱，并将其平均分配...
贪婪礼品送货员
一组NP（2≤NP≤10）唯一命名的朋友决定交换礼物的钱。这些朋友中的每一个可能或可能不会给任何或所有其他朋友一些钱。同样，每个朋友可能或可能不从任何或所有其他朋友接收钱。你在这个问题上的目标是推断每个人给予的收入多少。
赠送礼物的规则可能与您的期望不同。每个人都留出一定数量的钱来给予这笔钱，并将其平均分配给他或她给予礼物的所有人。没有分数钱是可用的，所以在2个朋友之间的3分别为1，剩下1个的朋友 - 剩下的1留在送礼者的“帐户”。
在任何一群朋友中，有些人比别人更多的捐赠（或者至少可能有更多的熟人），有些人比他人有更多的钱。
给定一群朋友，没有一个人的姓名长于14个字符，群体中的每个人花费在礼物上，以及每个人给予礼物的朋友的（子）列表，确定多少（或多少）少）组中的每个人给予他们。
重要的提示
分级机是使用标准Unix约定的Linux机器：行尾是一个通常称为“\ n”的单个字符。这与Windows不同，后者用两个字符'\ n'和'\ r'结束行。不要让你的程序被这个困住！
程序名称：gift1
输入格式
| 第1行： | 单个整数，NP | |||
| 线2..NP + 1： | 每行包含组成员的名称 | |||
| 线NP + 2..end： | NP组的线组织如下：
|
SAMPLE INPUT（file gift1.in）
5 dave 劳拉 欧文 vick amr dave 200 3 劳拉 欧文 vick 欧文 500 1 dave amr 150 2 vick 欧文 劳拉 0 2 amr vick vick 0 0
输出格式
输出是NP行，每个都有一个人的名称，后跟一个空白，然后是该人的净收益或损失（final_money_value - initial_money_value）。名称应以从输入的第2行开始出现的相同顺序打印。
所有礼物都是整数。每个人给予给予任何钱的每个朋友相同的整数金额，并且尽可能多地满足该约束。任何没有给予的钱都由提供者保存。
SAMPLE OUTPUT（file gift1.out）
dave 302 劳拉66 欧文-359 vick 141 amr -150
输出说明
五个名字：dave，laura，owen，vick，amr让我们保留每个人的货币表格：
| dave | 劳拉 | 欧文 | vick | amr |
| 0 | 0 | 0 | 0 | 0 |
| 首先，'dave'在'laura'，'owen'和'vick'中分裂200。那到达66每个，剩下2 | ||||
| -200 + 2 | 66 | 66 | 66 | 0 |
| 第二，“欧文”给了500给“dave”： | ||||
| -198 +500 | 66 | 66 -500 | 66 | 0 |
| 第三，'amr'在'vick'和'owen'之间分割150： | ||||
| 302 | 66 | -434 +75 | 66 +75 | -150 |
| 第四，'laura'在'amr'和'vick'之间分割0; 没有变化： | ||||
| 302 | 66 | -359 | 141 | -150 |
| 最后，'vick'给出0到没有人： | ||||
| dave | 劳拉 | 欧文 | vick | amr |
| 302 | 66 | -359 | 141 | -150 |
开始题目看错了，写了好几遍，换了好多种写法
-
//有BUG,23行编译不通过a/=b,a%b等无法计算;
-
//SIGFPE: Arithmetic exception
-
/*
-
ID:gwj11391
-
LANG:C
-
TASK:gift1
-
*/
-
#include<stdio.h>
-
#include<string.h>
-
int main(){
-
FILE* fin = fopen("gift1.in","r");
-
FILE* fout = fopen("gift1.out","w");
-
int T, i, j, k, a, b;
-
int NP_Pay[12] = {0};
-
char NP[12][16], NG[16];
-
fscanf(fin,"%d",&T);
-
for(i = 1; i <= T; i++)
-
fscanf(fin,"%s",NP[i]);
-
for(k = 1; k <= T; k++){
-
fscanf(fin,"%s",NG);
-
fscanf(fin,"%d %d",&a, &b);
-
for(i = 1; strcmp(NG,NP[i]); i++);//i <= T但是应该不会出现没有配对名字的情况
-
NP_Pay[i] -= a;
-
if(a%b == 0)a /= b;else{
-
NP_Pay[i] += a%b;
-
a = (a - a%b)/b;
-
}
-
for(j = 1; j <= b; j++){
-
fscanf(fin,"%s",NG);
-
for(i = 1; strcmp(NG,NP[i]); i++);
-
NP_Pay[i] += a;
-
}
-
}
-
for(i = 1; i <= T; i++)
-
fprintf(fout,"%s %d\n",NP[i],NP_Pay[i]);
-
return 0;
-
}
-
//C语言版本2，较长，其他OJ，已AC，未改文件输入输出
-
//取模计算，函数，结构
-
/*
-
ID:gwj11391
-
LANG:C
-
TASK:gift1
-
*/
-
#include<stdio.h>
-
#include<string.h>
-
struct{
-
char name[20];
-
int money;
-
}giver[11];
-
int solve(int);
-
int main(){
-
//freopen("gift1.in","r",stdin);
-
//freopen("gift1.out","w",stdout);
-
int NP;
-
scanf("%d",&NP);
-
for(int i = 0; i < NP; i++){
-
scanf("%s",giver[i].name);
-
giver[i].money = 0;
-
}
-
for(int sx = 0; sx < NP; sx++)solve(NP);
-
for(int l = 0; l < NP; l++)
-
printf("%s %d\n",giver[l].name,giver[l].money);
-
return 0;
-
}
-
-
int solve(int NP){
-
char owner[20];
-
int give_position,owner_position;
-
scanf("%s",owner);
-
for(int i = 0; i < NP; i++){
-
if(!strcmp(owner,giver[i].name)){
-
give_position = i;
-
}
-
}
-
//___________________________
-
int a, b;
-
scanf("%d %d",&a, &b);
-
//------------
-
if(a != 0){
-
giver[give_position].money -= a;
-
if(a%b == 0)a /= b;else{
-
giver[give_position].money += a%b;
-
a = (a-(a%b))/b;
-
}
-
}
-
//------------
-
for(int j = 0; j < b; j++){
-
scanf("%s",owner);
-
if(a != 0){
-
for(int k = 0; k < NP; k++){
-
if(!strcmp(owner,giver[k].name)){
-
owner_position = k;
-
}
-
}
-
//printf("%d %d\n",give_position,owner_position);
-
giver[owner_position].money += a;
-
}
-
}
-
}
//USACO已AC
-
/*
-
ID:gwj11391
-
LANG:C++
-
TASK:gift1
-
*/
-
#include<iostream>
-
#include<fstream>
-
#include<string>
-
using namespace std;
-
ifstream fin("gift1.in");
-
ofstream fout("gift1.out");
-
struct{
-
string name;
-
int money;
-
}giver[11];
-
int get_name(void){
-
int T;
-
fin>>T;
-
for(int i = 0; i<T; i++){
-
fin>>giver[i].name;
-
giver[i].money = 0;
-
}
-
return T;
-
}
-
int main(){
-
//-----------------------
-
int NP; //all name's number
-
NP = get_name();
-
//do--------------------
-
for(int i = 0; i<NP; i++){//每个人都送且只送一次礼物
-
int a,b,t;
-
string NG;
-
fin>>NG; //This name
-
fin>>a>>b; //recipient's money and people
-
//find giver
-
for(t = 0; t<NP; t++)
-
if(giver[t].name == NG)
-
break;
-
//every
-
for(int j = 0; j<b; j++){
-
fin>>NG;
-
//find recipient
-
for(int k = 0; k<NP; k++){
-
if(giver[k].name==NG){
-
giver[k].money += a/b;
-
giver[t].money -= a/b;
-
}
-
}
-
}
-
}
-
//Date out
-
for(int i = 0; i < NP; i++)
-
fout<<giver[i].name<<" "<<giver[i].money<<endl;
-
return 0;
-
}
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/54835683
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）