Question

用实现一个算法，验证成功后会再加30分。谢谢。最好用javascript,不行的话，用java或c++也可以。

有4个房间编号A，B ，C，D，分别可以往1，2，3，4个人，现在有10个人，允许每个人选择三个房间（第一、第二、第三志愿）。 可能出现以下情况：B房间原定2人，但有4人报名。如何去掉那2个人？有的房间没人报，如何把名额填满？写出算法，公平、公正地把每个房间的名额填满，并显示结果。

Answer 1

首先，对于全体10个人筛选第一志愿,对于某一房间,如果第一志愿衡胡对象数目大于改房间能旅念容纳最大值,则随机抽选,剩余人纳入等待分配序列。
第二，对于等待分配序列（这时小于10个人），重复上面处理，筛选第二志愿，剩余人纳入等待分配序列。
第三，拆拦困对于等待分配序列，重复上面处理，筛选第三志愿，剩余人纳入等待分配序列。
最后，对于等待分配序列，按照abcd的优先顺序，随机放入房间。

Answer 2

这个类似进程调度。
用人按DCBA顺序填满房间，按志愿优先级排人，同坦搜样模蔽优先级用随机抽取函数。假如有旦信州房间没人报、那么也只有一个房间就用剩下未被选的人填满。

Answer 3

可以用最大流算法，不过这里才四个人，直接枚举每个人住缺漏哪一间就行了
计算次败绝数是4的察扮姿10次方，100多万，完全，可以接受。

Answer 4

第一、二、三志愿是平等的还是具有优先级的？

追问

具有优先级。谢谢。

追答

10个人都随机选择3个不同的房间，那么每个人对A/B/C/D四个房间的渴望程度可表示为：第一志愿为3，第二志愿为2，第三志愿为1，无该房间志愿则为0，因此可用下列矩阵表示：
A B C D
第一个人： 3 1 0 2 ，即其志愿为（A D B）
第二个人： 2 0 3 1 ，即其志愿为（C A D）
第三个人： ...
...
第十个人： ...

首先搜集A列中为3的人，从中random出1个人住A房间，标记此人已住入A房间，如果为3的人数为0，继续，
搜集B列中为3的人，从中random出2个人住B房间，标记这两个人已住入B房间，如果为3的人数小于2，继续，
搜集C列中为3的人，从中random出3个人住B房间，标记这三个人已住入C房间，如果为3的人数小于3，继续，
搜集D列中为3的人，从中random出4个人住B房间，标记这四个人已住入D房间，如果为3的人数小于4，继续，

之后肯定有房间人多（假设为A,C），有房间人少（为B,D），这时候还有未分配房间的人（未标记住入房间，假设为N个人），矩阵如下：

A B C D
第3个人： 3 1 0 2 ，即其志愿为（A D B）
第5个人： 2 0 3 1 ，即其志愿为（C A D）
第7个人： ...
...
第9个人： ...

选出对B最感兴趣的人，random，住B，剩下的住D。