不看会后悔的Windows XP之经验谈	简单快捷DIY实用家庭影院

救命！某大公司程序员笔试题！答中有重奖！超难算法

楼主poyi_820921（）2006-03-30 09:50:27 在 Java / J2EE / EJB / JMS 提问

是的这样的：

有十种水果： a 有550个,b 有600个,c 有700个,d 有700个,e 有650个,f 有500个,g 500个,h 有600个,i 有600个,j 有500个

现在有个1000人小学校，要求把这些水果平均分到孩子手里

一年级 200人每人要求分到：9个

二年级 100人每人要求分到：8个

三年级 200人每人要求分到：5个

四年级 100人每人要求分到：3个

五年级 200人每人要求分到：6个

六年级 200人每人要求分到：4个

要求：要每个人手里实际分到的水果和要求分到的水果恰好相等，没人多拿没人少拿，

并且所有水果全部分完，一个不剩

还有一点要求，就是每个人手里的水果不能有重复品种的水果的，也就是说，比如：某人手里不能同时拿到两个A水果，这样是错误的做法

请各位老大救命，小弟谢了，最好发个源程序，任何语言做的都可以，发到xyz_133676984281@yahoo.com.cn里

我看行了，再和你联系，买你的源代码，谢谢

问题点数：20、回复次数：14Top

1 楼wizardblue（）回复于 2006-03-30 10:19:55 得分 0

按照每个人要求的个数降序排列
一年级 200人每人要求分到：9个
二年级 100人每人要求分到：8个
五年级 200人每人要求分到：6个
三年级 200人每人要求分到：5个
六年级 200人每人要求分到：4个
四年级 100人每人要求分到：3个

然后依次发过去
水果的种类按个数升序排列

起始状态
对水果按个数多少降序排
c d e b h i a j f g
700 700 650 600 600 600 550 500 500 500
发完一年级后
c d e b h i a j f g
700 700 650 600 600 600 550 500 500 500
-200
500 500 450 400 400 400 350 300 300 500

再对水果进行降序排
g c d e b h i a j f
500 700 700 650 600 600 600 550 500 500
500 500 500 450 400 400 400 350 300 300
发完二年级后
g c d e b h i a j f
500 500 500 450 400 400 400 350 300 300
-100
400 400 400 350 300 300 300 250 300 300

再对水果进行降序排
g c d e j f b h i a
400 400 400 350 300 300 300 300 300 250

再分五年级
g c d e j f b h i a
400 400 400 350 300 300 300 300 300 250
-200
200 200 200 150 100 100 300 300 300 250

再对水果进行降序排
b h i a g c d e j f
300 300 300 250 200 200 200 150 100 100

再分三年级
b h i a g c d e j f
300 300 300 250 200 200 200 150 100 100
-200
100 100 100 50 0 200 200 150 100 100

再对水果进行降序排
c d e j f b h i a g
200 200 150 100 100 100 100 100 50 0

再分六年级
c d e j f b h i a g
200 200 150 100 100 100 100 100 50 0
-200
0 0 0 50 0 0 100 100 50 0

再对水果进行降序排
h i a j c d e j f b g
100 100 50 50 0 0 0 0 0 0 0
再分四年级
h i a j c d e j f b g
100 100 50 50 0 0 0 0 0 0 0
-100
0 0 0 0 0 0 0 0 0 0 0

Top

2 楼wizardblue（）回复于 2006-03-30 10:31:20 得分 0

算法：我就用伪码写了自己改成某种语言的
Array f->水果的数组 f[i] 表示该种水果当前的数量
indexF->sort(indexF)使indexF 按f[i]值降序排列

Array g->要发水果的年级数组 g[i]表示该年级每个学生所要发的水果数
indexG->sort(indexG)使indexG按g[i]值降序排列

当前年级 gCurrent -> indexG[0];
do
给当前年级发所需的n种水果,(如果当前的某种水果数不足所需的数量，后面一种补充上来，并且要保证后面一种只发一次） (上面的例子中发六年级的时候可能处理不妥,即e 150 ,j100,)发完所需的200之后，j的50 不能再发)

f[i]->f[i]减去已经发的水果
indexF->sort(indexF)

while 所有年级还没有发完

Top

3 楼lilijr（beavers）回复于 2006-03-30 10:31:46 得分 0

仿照楼上一下
按照每个人要求的个数降序排列
一年级 200人每人要求分到：9个
二年级 100人每人要求分到：8个
五年级 200人每人要求分到：6个
三年级 200人每人要求分到：5个
六年级 200人每人要求分到：4个
四年级 100人每人要求分到：3个

水果的种类按个数降序排列
c d e b h i a j f g
700 700 650 600 600 600 550 500 500 500
按年级分发，每发一人水果的种类按个数降序排列一次，
依次去所需水果种类个数

这样效率低了一点，但算法简单一些Top

4 楼wizardblue（）回复于 2006-03-30 11:26:00 得分 20

也就O(n*n*log(n))Top

5 楼poyi_820921（）回复于 2006-03-30 11:41:37 得分 0

wizardblue(不死鱼) ,lilijr(beavers)大哥，谢谢你们先，可你们的用法我也用过了，最后的结果是，不是水果没分完，就是有人多拿，或少拿，拜托各位再想想，如果是一般的问题，我也不会拿来这里了Top

6 楼wizardblue（）回复于 2006-03-30 11:45:03 得分 0

最后不是
h i a j c d e j f b g
100 100 50 50 0 0 0 0 0 0 0
-100
0 0 0 0 0 0 0 0 0 0 0
了么？Top

7 楼wizardblue（）回复于 2006-03-30 11:47:07 得分 0

楼主上面的例子哪里有错误，或者是是几年级的学生多拿了么，帮么指出Top

8 楼poyi_820921（）回复于 2006-03-30 11:49:56 得分 0

我看懂了，谢谢，怎么联系？Top

9 楼lilijr（beavers）回复于 2006-03-30 11:54:59 得分 0

没有设定条件

就是当一种水果数目不过一个年级的学生事要有多个水果的组合Top

10 楼poyi_820921（）回复于 2006-03-30 11:55:04 得分 0

好人一生平安,wizardblue(不死鱼),我要向你学习,多多帮助弱者Top

11 楼wizardblue（）回复于 2006-03-30 11:55:10 得分 0

看来还得自己写代码，搞了半天Top

12 楼lilijr（beavers）回复于 2006-03-30 11:56:39 得分 0

这么多错字真是丢人

没有设定条件

就是当一种水果数目不够一个年级的学生时要用另一种水果的条件，每次派发水果都要有判断Top

13 楼poyi_820921（）回复于 2006-03-30 11:58:50 得分 0

还是CSDN好人多呀Top

14 楼poyi_820921（）回复于 2006-03-30 12:01:13 得分 0

已经发分给你了,wizardblue(不死鱼) ,想认识你,可以吗?交个朋友Top