USACO/gift1
来自"NOCOW"
- 这是USACO Chapter 1 .1中的OI题目Greedy Gift Givers的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
[编辑] 分析
这道题的难度相当于联赛第一题。 用数组incom outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j， inc(incom[j],outcom[i] div n)，其中n是要送的人数，最后inc(incom[i],outcom[i] mod n) 最后输出incom[i]-outcom[i]即可。（复杂度O(n^3)）
用Hash表可以进行优化，降复杂度为O(n^2)
PS:其实如果你用c++可以更好更快的解决问题，那就是STL中的map：
- include<iostream>
- include<fstream>
- include<string>
- include<map>
using namespace std;
int main()
{
string names[50];
map <string,int> reci,given;
int np;
ifstream cin("gift1.in");
ofstream cout("gift1.out");
cin>>np;
for (int i=1;i<=np;i++)
cin>>names[i];
for (int i=1;i<=np;i++)
{
string temp;
int tempr,tempg,j;
cin>>temp;
cin>>tempg>>j;
for (int k=1;k<=j;k++)
{
string temp2;
cin>>temp2;
reci[temp2]+=tempg/j;
given[temp]+=tempg/j;
}
}
for (int i=1;i<=np;i++)
cout<<names[i]<<" "<<reci[names[i]]-given[names[i]]<<endl;
return 0;
}
[编辑] 代码
pascal { ID:greenpz1 LANG:PASCAL TASK:gift1 } program gift1; var
g:text; a,b:array[1..10]of integer; name:array[1..10]of string; t,n,j,x,y,c:integer; s:string;
function search(s:string):integer; var
t:integer;
begin
for t:=1 to n do
if name[t]=s then begin
search:=t;
break;
end;
end;
begin
assign(g,'gift1.in');
reset(g);
readln(g,n);
for t:=1 to n do
readln(g,name[t]);
j:=0;
repeat
j:=j+1;
readln(g,s);
readln(g,x,y);
c:=search(s);
b[c]:=x;
if x>0 then
a[c]:=x mod y+a[c];
if y>0 then
for t:=1 to y do begin
readln(g,s);
c:=search(s);
a[c]:=x div y+a[c];
end;
until j=n;
close(g);
assign(g,'gift1.out');
rewrite(g);
for t:=1 to n do
writeln(g,name[t],' ',a[t]-b[t]);
close(g);
end.
