创新工场每年会组织同学与项目的双选会,假设现在有M个项目,编号从1到M,另有N名同学,编号从1到N,每名同学能选择最多三个、最少一个感兴趣的项目。选定之后,HR会安排项目负责人和相应感兴趣的同学一对一面谈,每次面谈持续半小时。由于大家平时都很忙,所以咱们要尽量节约时间,请你按照以下的条件设计算法,帮助HR安排面试。
1)同学很忙。项目负责人一次只能与一名同学面谈,而同学会在自己第一个面试开始时达到工场,最后一个面试结束后离开工场,如果参加一个项目组的面试后不能立即参加下一个项目组的面试,就必须在工场等待。所以请尽可能让同学的面试集中在某一时间段,减少同学在工场等待的时间。
2)项目负责人很忙。众所周知,创业团队的负责人会有很多事情要做,所以他们希望能够将自己参与的面试集中在某一段时间内,请在保证1)的情况下,使得项目负责人等待的时间最少。
3)HR很忙。从第一轮面试开始以后,所有HR都必须等到最后一轮面试结束,所以需要在保证1)和2)的同时,也能尽快解放掉所有的HR,即让第一轮面试到最后一轮面试之间持续的时间最短。
输入(以文件方式输入,文件名为iw,例如iw.in):
第1行...第n行:同学的编号 项目的编号
样例(数据间用空格隔开,两个0表示输入结束):
1 1
1 2
1 3
2 1
3 1
3 2
0 0
表示M=3,N=3,编号为1的同学选择了项目1,2和3,编号为2的同学选择了项目1,编号为3的同学选了项目1和2
输出(以文件方式输出,文件名为iw,例如iw.out):
第1行:编号为1的项目依次面试新同学的编号序列
第2行:编号为2的项目依次面试新同学的编号序列
...
第n行:编号为n的项目依次面试新同学的编号序列
样例(数据间用空格隔开,0表示没有面试):
1 3 2
3 1 0
0 0 1
表示编号为1的项目在第一轮面试编号为1的同学,第二轮面试编号为3的同学,第三轮面试编号为2的同学
编号为2的项目在第一轮面试编号为3的同学,第二轮面试编号为1的同学,第二轮不用面试
编号为3的项目在第一轮和第二轮都不用面试,第三轮面试编号为1的同学
|
|