经典百度面试算法题解

sowang

作者: Peak Wong, 　出处:IT专家网
http://database.ctocio.com.cn/dbzjdysummary/57/7676057.shtml



　【IT专家网独家】问： A厂有1万个工人，编号0-9999，( EE[10000] ), 1个厂长( GG )分派任务, 1个监工( MM )管理工人.厂子忙的时间不确定,可能突然很忙,1天接到任务5000多个,1个任务只能分配给1个工人做, 也可能好几十天没新任务.厂长分配任务给这1万个工人干，按工人编号一个一个来，到最后一个工人就又从头开始，任务完成时间各不相同，可能一个工人在分配任务的时候手里还有任务， 就得换下一个。


　　但是这1万个工人都很懒，领到了任务先不做，需要监工1个1个去问，如果工人有任务，就做，如果工人没任务，则不做。厂长只管分任务，1个1个来，可能几天也没新任务，不累;但是监工很累，监工每天都要看所有工人的情况，即使这些工人都没有任务, 实际上每天工人(80%左右)是没任务的，请问，怎么让监工的工作轻松下来. 比如说每天只问1小半工人.

　　Peak Wong:

　　分析如下：

　　因为“任务完成时间各不相同” ，所以有可能a，b，c某天都有任务，但b的任务最先完成，那么当b的任务完成后，有任务的人的工号可能是不连续的;

　　用一个数组表示1万个工人是否有任务，并保存最后被分配任务的人的工号;

　　1)从前一天“最后被分配任务的人的工号”开始，依次问下一个工号的人，置对应的工作状态，直到碰到前一天无工作，且当天也无工作的人;并更新当步最后有工作的人的工号为当天的“最后被分配任务的人的工号”;

　　2)从前一天“最后被分配任务的人的工号”开始，依次问上一个工号且前一天有工作的人;

　　问题是监工可以知道那些信息，否则还不是一个一个接着去问。

　　还有就是tailzhou的步骤1消耗的时间T1， 工人完成的时间T2,如果T2 <T1，那么中间就会断开。　　所以很多条件都没有限制。