USACO/gift1

这是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(见c++代码3)：

代码

C

C++

Pascal

Java

引用

[1]

[2]