一道百度面试题

A厂有1万个工人，编号0-9999，( EE[10000] ),  1个厂长( GG )分派任务,  1个监工( MM )管理工人.
厂子忙的时间不确定,可能突然很忙,1天接到任务5000多个,1个任务只能分配给1个工人做, 也可能好几十天没新任务.

厂长分配任务给这1万个工人干，按工人编号一个一个来，到最后一个工人就又从头开始，任务完成时间各不相同，
可能一个工人在分配任务的时候手里还有任务， 就得换下一个。

但是这1万个工人都很懒，领到了任务先不做，需要监工1个1个去问，如果工人有任务，就做，如果工人没任务，则不做。
厂长只管分任务，1个1个来，可能几天也没新任务，不累；
但是监工很累，监工每天都要看所有工人的情况，即使这些工人都没有任务, 实际上每天工人（80%左右）是没任务的，
请问，怎么让监工的工作轻松下来. 比如说每天只问1小半工人.
---------回复--------------
因为“任务完成时间各不相同”
所以有可能a，b，c某天都有任务，但b的任务最先完成，那么当b的任务完成后，有任务的人的工号可能是不连续的；

用一个数组表示1万个工人是否有任务，并保存最后被分配任务的人的工号；
1）从前一天“最后被分配任务的人的工号”开始，依次问下一个工号的人，置对应的工作状态，直到碰到前一天无工作，且当天也无工作的人；并更新当步最后有工作的人的工号为当天的“最后被分配任务的人的工号”;
2）从前一天“最后被分配任务的人的工号”开始，依次问上一个工号且前一天有工作的人；
---------回复--------------
问题是监工可以知道那些信息，否则还不是一个一个接着去问。

还有就是tailzhou的步骤1消耗的时间T1，
工人完成的时间T2,如果T2 <T1，那么中间就会断开。

所以很多条件都没有限制
---------回复--------------
就是监工要记录所有工人的工作状态，然后每天只查询在工作的工人就可以了。（并且记录谁还在工作中）
其实最根本的解决之道是在每次厂长分配任务时，监工也被通知谁被分配了任务。而现在题目的假设是厂长太忙了，来不及通知监工（其实让监工分配就行了）。
解决这个问题很简单，监工只要记录（也可能是他猜测）上次厂长分配任务最后分配到那个人就可以了。
然后每天查询时，除了监督前一天来在工作的人外，还要查看从上次分配到任务的编号的下一个编号开始的工人，向后依次查询，知道遇到一个没有被分配工作的人（这个工人后面不会再有人被分配任务了).同时监工还要记录或猜测哪个工人是当天最后被分配任务的。在“查看从上次分配到任务的编号的下一个编号开始的工人，向后依次查询”过程中，如果工人的话可信，询问他们就可以了。如果不可信，那么可以猜测为最后一个昨天空闲，今天忙的工人就可以了。
其实，监工既然可以监督，他总得有渠道知道当天那个工人还有活要做（不然所有工人都可以说今天我没有任务呀），所以没有这么复杂的问题。
---------回复--------------
官管民，民养官，成立一个领导层，让MM来管理领导层就OK了
---------回复--------------
关键字定为任务，登记如下信息：
任务  工人号码  接受任务时间 完成任务时间
厂长在分配任务时登记
然后细节性问题根据实际情况分类，比如工人如果完成任务是否会自动上报，如果是，那么问题就相当简单，每天只要根据任务去询问对应的部分工人即可。如果不是，则需要自己去问那些任务对应的工人，如果完成则做好记录，在厂长没有分配新任务之前（厂长分配任务时更新表），不需要再次查询，如果厂长有分配新任务，那么以完成任务对应的工人号码查表看是否有新任务分配，如果有，重复询问，如果没有则不需查询。
不知道理解对没有，有没有标准答案？
---------回复--------------
设置一个头指针，初始为0；
设置一个尾指针，初始为9999；
从0向后循环检测，如果有工作（或者未完成）则与头指针的位置交换（相同则不用交换，下同），同时头指针+1；如果无工作（或者已完成）则与尾指针的位置交换，同时尾指针-1；
如果发生了交换，重新检测当前位置；
结束条件：尾指针>=头指针，或者当前位置>尾指针。

---------回复--------------
这是一个类似 apche 早期实现内存池的算法，轮询法。
C++ primer 给了一个用链表实现的常数为一的算法。effective C++ 里面也有。
你可以看看
---------回复--------------
估计他们要实现自己的某个池算法。
---------回复--------------

to mathe：同时监工还要记录或猜测哪个工人是当天最后被分配任务的


这个如果成立的话，没有理由不能假设监工知道当天哪些工人被分配了任务。
---------回复--------------
好像这题貌似假设监工根本不知道厂长的存在
---------回复--------------
到最后一个工人就又从头开始


到最后一个就说明所有工人都有任务了，怎么还能从头开始呢？

---------回复--------------
题目信息不足
---------回复--------------
后面的分配任务时，前面的可能已经完成了。

---------回复--------------
请问，怎么让监工的工作轻松下来？？？？？

什么算法啊？？？


---------回复--------------
现记下来了，回去在想象
---------回复--------------
可以修改厂长的工作方式吗？
---------回复--------------
我想能不能这样，在厂长分配任务的时候监工站在旁边，分一个就问一个，然后再问上一次任务没有完成的人，完成了就将此员工的名字在上一次的任务中划去。这样往复。
---------回复--------------
我想能不能这样，在厂长分配任务的时候监工站在旁边，分一个就问一个，然后再问上一次任务没有完成的人，完成了就将此员工的名字在上一次的任务中划去。这样往复。
---------回复--------------
能不能这样，厂长分配任务的时候把分配的任务的工人记录下来，监工按照厂长的记录去问有工作的人是否已经开始工作了。工人工作完了就把自己从有工作的名单中除去。
写写看这个算法，呵呵不要见笑


1.厂长分配任务，同时用一个数组或者链表work记录下分配到任务的工人
2.监工去询问在work中有记录的工人工作是否已经开始
3.被询问过的工人都已经开始工作，监工把他们从work记录中除去。
1 2 3应该可以一起执行，work设为临界区。

---------回复--------------
study,有没有标准答案啊

---------回复--------------
1万的bit记录厂长的工作. = 1250byte;
1个链表记录监工的工作. => 大小未知道;
需要互相通知对方.
---------回复--------------
不懂，题目都没懂，应该有提示吧，面试的时候没问吗？
---------回复--------------
不会，留个记号，回头再看。
---------回复--------------
我想做这个题目,可是楼主没有给全题目.
---------回复--------------
监工要记录正在工作的工人，然后根据任务所需的时间和新的任务数，计算出新分配任务的工人，只查看新分配的工人
---------回复--------------
只是监工能不能得到所需要的数据，这个好像题目中没有说啊
---------回复--------------
mark

---------回复--------------
路过学习！~~~~~~~~~~~~~~~
---------回复--------------
study
---------回复--------------
mark
---------回复--------------
每一次分配任务后，监工询问后记住最后一个有任务的员工的ID，下一次从有任务的ID的下一个开始问，问到第一个没有任务的，记住他的ID，依此类推
---------回复--------------
监工买几个大喇叭，每天先广播一下，没任务的到操场集合做体操去（监工管工人嘛，做做体操没有坏处），有任务的留在原位，这时监工就可以到工厂一个一个问去。哈哈
---------回复--------------
楼上的全部不对！！！

看清楚题目，
1、工人都很懒，不会主动上报自己没有工作。
2、“前天安排到的最后一个工号”以后的工号，不可能就能肯定他们手头没有工作：比如分到10000号了，下一轮肯定从1号开始，但是你确定1号手头没有工作?所以这种假设不能满足一轮过后的情况。
3、有人说厂长很忙，请看清题目。厂长很空闲！
4、思维肯定要从厂长和监工入手，改变他们的工作方式，而不是工人，因为工人数量太庞大，无法控制。

---------回复--------------
既然每天80%的工人是没有任务的，那每天问20%-30%（或者25%那么两天就有5000工人状态可知，用于1天5000件任务)的工人就可以保证任务能够分配下去，厂长就是个机器人，他只需记录他要依次分配任务的工号，如果没有监工，10000个任务分配完毕后将再也无法分配任务，因为现在工人都有任务，不过只要监工不问，他们就不干活
所以监工只要第一天掌握所有工号情况，以后每天掌握1/4的工号即可，有任务就干活，没任务的就歇着，其他的不用管，分配任务是厂长的事
---------回复--------------
15K-20K是多少？？
---------回复--------------
同意31楼想法。

监工将有工作的员工ID记录下来：

第一天时，从ID为1的员工开始，问有没工作，并记录员工ID。比如：1 2 3 4
以后每一天，监工记录上一天有工作的员工的最大ID(4)，并问他们是否完成工作，完成就删除ID。再从最大ID+1(ID+1>10000时，ID=1)，开始问员工，将有工作的员工ID记录，遇到第一个没有工作的员工时，监工的事也就完成了。
---------回复--------------
工人很懒，并没有说他们不诚实呀，呵呵
---------回复--------------
MARK
---------回复--------------
偶觉得本题的关键是“工人拿到任务一定不会主动开始做”这一点，也就是说在监工MM问到的时候才是工人真正开始做的时候。如果这时候能知道任务大致完成时间就好办，如果不知道，至少也能知道他是刚刚开始任务，下一轮查询的时候可以把他放在最后。即一个链表，始终把查到刚开始干活的人放到最后，而每次只查链表的前面一部分人。
---------回复--------------
顶一个
回头慢慢看看
---------回复--------------
up
---------回复--------------
工厂设立奖励机制，谁最先最好完成任务的给予最大奖励，次快的给予次好奖励。

这样 监工就能最快最好的知道工人的工作情况了。 并且 长久以往还能知道工人的工作效率，哪些可以重用 哪些不能用。


---------回复--------------
进程（线程）轮询策略
bitmap
排序算法
因为厂长太牛逼，不可能安排任务的时候通知监工的，所以监工只能轮询。
1 第一次轮询，把有工作的人号码记下来，知道找到所有没有工作的人，找到第一个没有工作的人的号码，也记下来
2 把有工作的人按照工作结束时间排序，从前到后
3 每隔一段时间问一下有工作的人，如果工作结束在下一天的，不再问了，反正工人懒，不会提前完成的。最差的状态是每个都要问，占工人总数的20%
4 每隔一段时间，问一下第一个没有工作的人，a)如果有工作，把他排入到有工作的人的列表中去（插入时排序），并且问下一个号码的人（如果这个号码在有工作的人列表，忽略，再下一个），b)如果有就重复a，如果没有就记住这个号码。
5 每隔一定时间做3，4；重复做即可，如果发生号码范围大于工人总数，号码又从0开始。

---------回复--------------
题目应该明确：如果工人有工作，监工告之以后，这个工人就会一直做下去，直到这项工作完成；
在这种条件下，监工的工作一日流程如下：
1）从前一天最后一个没做工作的工人位置开始询问（如果位置>9999，从0始）
2）到第一个没有分配工作的员工结束，并记录这员工的位置。监工休息！


---------回复--------------
呵呵，1）从前一天第一个没做工作的工人位置开始询问（如果位置> 9999，从0始）
2）到第一个没有分配工作的员工结束，并记录这员工的位置。监工休息！

---------回复--------------
不对！！！
思路错误，郁闷ING
---------回复--------------
mark
---------回复--------------
mark
---------回复--------------
要想让监工轻松下来，就要把工人分类，哪些工人有任务，哪些没有任务。

监工要想知道这些信息就要向厂长问，因为厂长管分配任务的（厂长分配谁了，监工就去查谁），厂长分配任务的时候，工人也有两种状态，是接受--工人空闲，二是拒绝--还有工作；也就是

说不管工人接受与否，监工都要去查（没分配任务的就不用查了）。

所以我的结论是，要想让监工轻松，就要保持监工和厂长间的通讯，监工要轮询厂长都分给了谁任务，然后监工去查看。
---------回复--------------
可以让系统维护一个类似于windows里面的ready summary的数据结构，这样的话，监工只需要查询这个位图就知道谁忙谁闲了。
---------回复--------------
看看……学习
---------回复--------------
mark 学习
---------回复--------------
mark 看看
---------回复--------------
楼主，你能确保题目没记错

正如楼上一位朋友所问：监工是不是问了以后，工人就会一直把工作做完？
如果这样的话，最简单的一个考虑，他第一次问的时候记住这个工人今天能否做完，不能做完的话，哪天才能做完。
监工实际上只需要在工人做完了以后的第二天去问就可以了。因为不做完，厂长不会给他分新任务。
但
楼主说：但是监工很累，监工每天都要看所有工人的情况，即使这些工人都没有任务
那又不一样了，就是说监工必须每天问，不然工人不会开始工作。
这时候就是没有工作的工人不需要问。
首先工作队列，每个人问一遍，今天能做完的移到空闲队列。
空闲队列，二分查找，找到非空闲的，往前处理完，今天能做完的不动，不能做完的移到工作队列。
很简单的问题阿。二分查找需要问的人非常少的。
绝对能满足楼主说的：比如说每天只问1小半工人

用我的方法厂长分任务的时候不需要通知监工。
实际上通知也没有意义，因为是按顺序分配，监工实际上需要知道的是今天有多少新任务。
就算不知道，用二分查找10000人也最多需要10几次。
这10几次，再根据实际上每天工人（80%左右）是没任务的，所以实际上每天问的人只有20%左右。
---------回复--------------
这个题目做高程考试题还凑合。

---------回复--------------
根本就是条件不足，自由发挥吧
---------回复--------------
条件好像够，上面的想的有错，有时间再做个详细的解答
---------回复--------------
把任务也按编号来分
从0到9999,到9999了又从0开始,新任务接上一次任务后面的编号
因为80%的工人是没任务的
那监工就按任务编号来问
如任务编号是2000号
那就问2000号工人
这样问的人会少吧
不过这是让监工来分派任务了

不知题目是不是厂长先直接从工人1开始直接分派任务不管有该工人有没有任务
然后让监工来调整
如果是这种情况就不行了

---------回复--------------
监工自己有个表存放当前有活的人

1 进入这个表的规则
厂长分配了任务给这个工人(前提是厂长和监工有沟通)

退出表的规则
某天去查，此工人没有活

2 如果监工和厂长没有沟通，可以假设厂长在第一次有任务首先给1#。

监工init:
chk=1;
list=empty;
监工循环 每天一次
{
    check(every one in list);
    从chk起,一直check,chk++(加到头就转回来), 直到有没有任务的人为止；
    {
      如果 有任务的enlist(不重复);
    }
}
---------回复--------------
靠，够难的
---------回复--------------
首先有一个工人管理表，用于管理工人工作状态，
再引入一个任务分配表，用于记录正在工作的工人的编号， 伪码如下：

while (继续运行）
{
    监工遍历任务分配表，根据表中记录的工人位置到工人管理表中查询，
    若工人工作已完成，则从表中删除，并更新工人管理表；
   
    while(厂长还有任务需要分配）
    {
      从上次分配结束后的位置开始查找，直到找到第一个空闲的工人为止；
        厂长为该工人分配任务；
        监工将该位置记录至任务分配表中
        移动分配位置；
    }
    监工再次遍历任务分配表，根据表中记录的工人位置到工人管理表中查询，
    若工人工作已完成，则从表中删除，并更新工人管理表；
    若工人尚未开始工作，则使其开始，并更新至工人管理表中
}

分析：引入任务分配表之后，监工只根据表中所记录的工人进行查询并进行更新，而无需遍历整个工人管理表。
另外更重要的是，只要能够保证：
1、厂长在分配任务之前工人管理表能够反映出工人工作的最新状态。
2、在厂长分配完任务之后工人能够马上开始工作。
满足以上两个条件，监工的任务就完成了，无需每日更新工人管理表，只需在厂长开始分配任务之前和分配完任务之后对
任务分配表处理即可。但这又基于一个假设，即监工知道厂长何时开始分配任务，若不知道的话，则监工需每日依照任务
分配表中的记录对工人管理表进行更新。



---------回复--------------
1.问题分析
    现在的情况是监工每天要查看所有的工人，催他们工作，因为不催他们不开工，即要访问EE[10000]的每个元素一次。目标是每天只问一小半的工人，实际上没有工作的工人是不需要问的，最理想的情况就是监工只问有工作的工人，或者尽可能少地问没有工作的工人，即要尽可能少地访问EE[10000]的元素。
  怎么办呢？监工想了一个办法，他做了一万张卡片，每张卡片上写着工人的编号，从0-9999，恰好和数组EE[10000]的下标对应。
    监工拿着他的秘密武器上阵了，0号，有工作没？没有。好，放右边口袋。1号，有工作没？有。今天能干完吗？能。好，放右边口袋（并且放在0号后面）。2 号，有工作没？有，今天能干完吗？不能。嗯，放左边。3号，没有。放右边（1号后面）。4号，今天干不完，放左边。……第二天，先看右边（昨天没事的）， 0号，有工作没，有，今天能干完吗，能，好，不动。1号有工作没，有，干不完，好，放左边（接着昨天后面放）。3号，没有，哦，厂长GG还没有分配到这里阿，那明天检查空的从这里开始就可以了（记住)，但今天仍然轻松不了，因为可能是从后面的号码过来，并且分配到前面来了。右边全部查完了。再查左边。2 号，今天能干完，放右边（并且放在0号后面）。阿，又碰到了1号了，今天的检查结束。第三天，总算可以轻松了。从3号开始，先查右边。今天做得完，不动，做不完，移到左边后面，碰到没有任务的，或者碰到3号，右边检查完。再看左边，做得完的，移到右边，并且按顺序插入其它卡片中间，做不完的，不动，直到碰到今天新加入的做不完的，或者整个左边的卡片都检查完。
  说了这么多，实际上就是左边的是工作的队列，右边的是没工作的队列，左边和右边的区别就是右边的要保持按编号排序（因为厂长GG分配任务是按顺序分的)。再拿支铅笔，在有的卡片上做做记号。工作轻松不少。以上都是假设工人必须每天催才会工作，并且监工每天都是在厂长分配任务之后才去催。如果工人催一次就会一直工作，那么简单，监工只需要在卡片上记下还要几天才去问就行了。如果监工是每天早上去催，厂长去可能在清早（问之前）或下午（问之后，但工人还没工作完）去分任务。
如果是前者，当然没问题，如果是后者问题来了，因为3号是今天才能完工的，但也是放在右边，如果厂长刚好分了2号和4号，那么按上面的逻辑，4号就催不到了。
所以为了避免这种情况，当天能完的还不能放在空闲里。嗯，只要再准备一个口袋就行了。好在监工的衣服上面有两个口袋，下面也有两个，用了下面两个，上面还有两个没有被使用。拿一个来用就行了。
检查下面的左右口袋时，凡是当天能做完的，都放在左上。OK，先右下，再左下，当天能做完的这会儿放右上，再把左上的按顺序插入右下。应该没问题了吧，不管厂长何时分任务，监工只需要看自己的口袋就可以了。右下需要访问的是从昨天访问的没工作的开始，再到一个新的没工作的。左下都要访问。右上或左上的卡片只需要整理。因为实际上每天工人（80%左右）是没任务的，都在右下，并且也可能好几十天没新任务，这下轻松了，只用问小部分工人就能保证工作正常进行了。
好了，如果想先模拟一遍怎么办，用大脑模拟，10000人太多想不过来，累。写个程序吧。要写程序得先有算法。
2.算法
  以下算法模拟最一般的情况，即监工不知道厂长何时分任务，厂长在一天的任何时候都可以分任务，工人每天都要问才工作，监工只在早上去催（为了简化工时的计算，即工时以天为单位）。
  完全的随机起点模拟，即此方法可从任何监工想要采用此方法的时间点开始。
  假设一个任务完成的时间是1-N天，厂子一天接到的新任务数是0-M个。用T分钟模拟一天。定时器是精度毫秒级。
  A.用0-N之间的数初始化EE[10000]，模拟当前工人的工作状态。EE[i]表示工人还要多少天完成这个任务。EE[i]=0，表示没任务。
  B.设置定时器，厂长分任务定时器为1-T*60*1000毫秒之间某个时间，监工定时器设为T*60*1000毫秒。
  C.厂长定时器到，厂长分任务。用c记录厂长从哪里开始。第一次时有个随机初始化的工程，随机一个0-9999之间的数，然后找到第一个EE[i]=0的i，从这个c=i开始分配。
    随机产生0-M，如果=0，则 c=i不变，如果是1-M之间的值，则一个个查，碰到EE[i]=0的，给他随机一个1-N的值，直到分完这些任务，并且c=最后分到的+1。这个题目是研究监工的问题是，厂长比较轻松，下次让他继续从这里找下去。
    重新设定厂长定时器，定时为T*60*1000-上次定的时，再加上1-T*60*1000毫秒之间某个时间,因为厂长也只会一天分一次，所以先要把今天的时间用完，再加上下一天的某个时间，（从前面可以看出，厂长的定时器设成T也是一样的，只要考虑一下访问共享数据的问题，这里先不考虑这个问题）。
  D.监工定时器到，监工问工人。
    新建四个链表。a（今天还不能做完的）,b（没有工作的）,c（今天可以做完的）,d（今天可以做完的），初始化为空。但b为有序链表。c和d轮流使用。
    第一次定时到，访问EE[10000]，今天不能做完的(EE[i]>1)接到a的尾巴上，能做完的(EE[i]=1)接到c的尾巴上，没有工作的(EE[i]=0)接b，d空。
    第二次定时到，访问b，今天不能做完的接到a的尾巴上，能做完的接到d的尾巴上，并且记录出现有工作的人后再出现没有工作的人的结点指针p。如果没有这样的人，那就是链表第一个人或者为空（大家都有工作）。但不管怎样必须把整个链表b访问一遍。
        访问a,不能做完的不动，能做完的接到d的尾巴上，最后将c中的元素插入b。注意，链表中元素唯一，也就是说移到另一个链表的时候，也意味着从原链表删除。
    第三次定时到，从p开始访问b中的元素，今天不能做完的接到a的尾巴上，能做完的接到c的尾巴上，直到找到一个没有工作的或者已经全部找了一遍（找 的时候调整p到新的位置）。到链表最后一个后，可能要从头找。
          访问a,不能做完的不动，能做完的接到c的尾巴上，最后将d中的元素插入b。
    第四次定时到，和第3次类似，只是c和d的位置对调了一下。到这时，监工的工作已经轻松了，整个系统将按这个新的方式一直运行下去。
  监工的定时器不需要重新设置。
  a,b,c,d中的元素内容为工人编号，访问时语法类似if(EE[p->index]>1) 。

3.程序
  省略。
---------回复--------------
http://www.lua.org/pil/9.4.html

GG = main program
MM = dispatcher
EE = coroutine
---------回复--------------
请问，怎么让监工的工作轻松下来. 比如说每天只问1小半工人.

这么简单的题目，还找什么算法.

找个助手就行了，自己问一半，助手问一半.
---------回复--------------
ahjoe
那还不如要助手都问了，监工回家去，最轻松
---------回复--------------
看样子是监工每天都要摧一遍工人，工人才开工。
我们假设从第一天开始，厂长分配工作，监工检查工作，从第一个人开始，直到遇到一个没有工作的工人，监工停止检查（工作为顺序分配，所以后面的人不会被分配到工作），监工把这些人的工号记录在自己的工作表内，并记下最后一个工人的工号。
第二天，监工先检查昨天工作表内记录的工人，如果完成，就从工作表中删除，接着从昨天最后一个分配到任务的工人开始，继续往下检查，直到遇到没有任务的人，再把今天新有任务的添加到工作表内，依次类推。

我的思想就是，监工不能知道工人完成任务的时间，所以每天要检查昨天还有任务的人和今天新有任务的人。


---------回复--------------
因为最多只5000任务，所以可将工人编组，每2个人算一组，每天次分配任务，一个组只分配一个，每次查询也只查询每组中的一个
---------回复--------------
A厂有1万个工人，编号0-9999，(  EE[10000]  ),    1个厂长(  GG  )分派任务,    1个监工(  MM  )管理工人.
厂子忙的时间不确定,可能突然很忙,1天接到任务5000多个,1个任务只能分配给1个工人做,  也可能好几十天没新任务.

厂长分配任务给这1万个工人干，按工人编号一个一个来，到最后一个工人就又从头开始，任务完成时间各不相同，
可能一个工人在分配任务的时候手里还有任务，  就得换下一个。

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


//------------------------------ ----------------------
意思是任务只分配给连续编号的人？“可能一个工人在分配任务的时候手里还有任务，  就得换下一个”那没完成的工作怎么办？

是不是可以用递归调用来做，厂长把第一个人的任务分配为监工的助手，后面检查的事情由ta负责，然后向监工汇报，OK
然后监工和厂长过上了幸福的生活
---------回复--------------
是不是可以用二分法

根据项目的预期来分组 分组后 每组按顺序分号 再  配合二分法
就是先确定出明天一定会有任务或 一定不会有任务的 如果不足再 问不确定是否有任务的 so on
---------回复--------------
换下一个的意思因该是换下一个人来接任务,而不是叫有任务的人换新的任务
我同意67楼的,将工人编组，每2个人算一组，每天次分配任务，一个组只分配一个，每次查询也只查询每组中的一个
---------回复--------------
像绕口令。
学习
---------回复--------------
关键在于“80%左右的人没任务”...
所以我们可以"以空间换时间",使用20%的存储空间来换取80%的计算时间,
即:

厂长分配任务时,如果给某个人分配了任务,那么在"已分配任务"的链表中加上指上这个人的指针,
这个人完成任务后移除...

监工就对"已分配任务 "的链表进行操作就可以了
---------回复--------------
可能几天也没新任务，不累； 但是监工很累，监工每天都要看所有工人的情况，即使这些工人都没有任务,  实际上每天工人（80%左右）是没任务的，

所以应该重点是优化监工的工作,而不是优化厂长的工作,
当然全部优化更好...
但有冲突时,优先考虑监工的优化
---------回复--------------
这个不能纯粹从程序角度考虑，而要从数学角度考虑解决。
初步看了看，感觉用到了数学的概率论，再具体一点就是运筹学里的排队论，好象有相应的数学公式的
数学学的好，做什么都轻松啊，写了多年程序，就这一个体会。可惜没学好，所以还在编程。
看史玉柱都身价几百亿了，浙大数学系的，就是不一样，唉
---------回复--------------
LS的强，但是能不能给出个算法
---------回复--------------
应该直接XX MD 。

---------回复--------------
搞不清楚，这个题目要干吗？如果是数学问题，那么可以试试这个：
把这些人分成K组，每组检测一次（所有人的状态取或运算），如果该组为空闲，那么不管
如果该组忙，则继续分成K组，直到结束。

K的取值与空闲率有关
---------回复--------------
呵呵，这是软件中的常见问题，换个马甲变成“GG、MM、工人、厂长”就不认识啦~~~

监工就是Monitor，就是Viewer啊，工人就是各个干活的线程(Worker)，厂长就是Task   Manager嘛。用过电驴子吗？用过FlashGet吗？类似。

题目中的Monitor是用轮巡方式查询各Worker的状态，是主动查询，这样效率很低。既然主动查询效率低，那就改成被动的呗。让工人自身状态一改变就向监工报告。而监工那里维护一张有工作在做的工人列表，刚拿到工作的加到列表里，工作做完的从列表里删除。更进一步，这张表可以作为厂长分配工作的参考，分配工作时可以向监工索要这张表建立无工作工人表（补集）。

这就是设计模式里的“观察者”模式。



---------回复--------------
工人有三种状态嘛.
0.无工作
1.有工作没做
2.有工作在做

监工需要做的是记录前天最后一个有状态2的工作编号。从此工人下一位( 到最大编号后从0继续)开始查询工人状态直到有工人为状态0。查询动将导致状态1的工人进入状态3。
---------回复--------------
mark

---------回复--------------
我也正在琢磨该问题解。
---------回复--------------
监工 应该只跟踪任务的进度，并记录任务的实施者（工人）；
给厂长汇报的也只是这些有任务的工人的ID
任务怎么分配，长厂负责，（他不是很闲吗）
---------回复--------------
这不是健康中心的排号算法嘛.
只不过是小姐不会报钟而已.
小姐不报钟,那就排号,然后问咯.
哪个不到钟的,就重新拍一次就OK了.

---------回复--------------
不就是线程调度算法么？Ready队列表示有工等着做的，free队列表示没事做的，busy表示正在做事的
三个队列管理即可
---------回复--------------
我给出的方法最简单，把工资制度改一下，基本工资加计件奖金，然后每个工人就会抢着做完手上的工作，否则，如果下次轮到他的时候工作没做完的话，就会跳过他，影响他的收入。这样一来，监工根本就不需要去过问。一个团队的一线工人都很懒，不是个人人品的问题了，应该从制度入手
---------回复--------------
我的方法是每个人领到任务和完成任务自己去监工那里上报，监工记录工作情况，工资根据监工的记录发。这样就不需要监工一个一个的问了。
---------回复--------------
mark


---------回复--------------
厂长分配任务有规律,监工的工作就可以轻松下来
15K-20K级, 高程惨被鄙视... 什么意思?
题目不难呀
1.第一次监工问所有工人的状态(空闲或工作+ 时长),并得到最后任务人
2.第二次监工换算所有工人的状态(本来空闲的不换算当然省事)
3.监工从上次最后任务人后,依此(要敦促工作)问空闲工人的接任务的状态并敦促工作,直到最后任务人
4.循环2,3
---------回复--------------
1.第一次监工问所有工人的状态(空闲或工作+时长)并敦促工作
2.下次,监工换算所有工人的状态(本来空闲的不换算当然省事)
3.监工依此(要敦促工作)问空闲(只有空闲的才会分道任务)工人的接任务的状态并敦促工作,并找到最后任务人
4.如没人有新工作,循环2,3直到找到最后任务人
5.下次,监工换算所有工人的状态(本来空闲的不换算当然省事)
6.监工从上次最后任务人后,依此(要敦促工作)问空闲(只有空闲的才会分道任务)工人的接任务的状态并敦促工作,直到最后任务人
7.循环5,6
---------回复--------------
我的分析如下:
  1、当有任务来的时候,监工只需要找到任何一个完成任务的工人.
  2、让这个工人和监工一起去找其他完成任务的工人。
  3、每找到一个完成任务的工人，就让此工人也加入到找没有任务工人的行列中去。
  4、直到找到的工人数=任务数，或将所有工人都询问过或停止。
  5、厂长分配任务。
  6、如果找到的工人数少于任务数，监工继续查找。
  7、重复1-5。


---------回复--------------
mark
---------回复--------------
mark...
---------回复--------------
只要设定完成任务的工人都可以吻一下监工( MM )，那么监工( MM )就不用再问工人了，
这样可以让效率得到最大程度的提高，还有一个方法就是把一万个工人全部换掉，这个
执行起来有点麻烦
---------回复--------------
MARK
---------回复--------------
mark
---------回复--------------
每天监工都去问厂长，把最后分配的工人ID记下来
然后查询昨天的最后ID和今天的最后ID之间的
也就是说，只查询当天分配出去的工人ID
---------回复--------------
MARK!
---------回复--------------
mark
---------回复--------------
1万工人哪能一个mm管啊，工人分50个组，mm管组长，。。。
---------回复--------------
关注。。。
---------回复--------------
厂长分任务总有一个记录表吧(分一个就记录一个),监工只管从这张表里面的工人去问就行了啊(问一个就从表里删除).
---------回复--------------
真是不会，看不出跟程序有啥关系
---------回复--------------
如果能知道任务完成的时间就好了，
MM拿到任务，先按照任务所需要的完成时间从小到大排一遍，
然后从上次安排结束的最后一个人开始询问，并记录下该工人完成时间，制作工人完成时间表，以便下次安排。

领到任务后先根据离上次任务安排的间隔时间和记录的工人完成时间表，计算出本次不能安排的工人号数的范围，再从上次结束的号数开始安排，（应该也可以后面在计算号熟范围吧），重复几次，MM以后再问的话，基本就是按顺序（排除不能安排的工人号数）安排就可以了。

。。。思维混乱ing~~~~~~

---------回复--------------
Mark
---------回复--------------
有意思。这样就是管理问题了撒
---------回复--------------
感觉题目确实不是很清楚，我理解如下：
1 ， 只允许设计监工的工作方式
2 ， 工人只在领到新任务时候要监工询问才能开始工作，一旦开始 ，就会一直把工作做完
3 ， 工人按时完成任务
解决思路
1， 监工每次讯问工人就记录工人ID和工作结束时间（以天为单位）
2， 监工维持两个集合一个标记，一个集合记录现在在工作的工人ID（按工作结束时间有序），一个集合记录记录
    空闲工人ID（按工人ID有序），一个标记是记录第一个被讯问到时没有工作的工人的ID（起始值是第一个工人）
3， 监工每天的工作是，先察看第一个集合，把今天该结束工作的工人移到第二个集合里，然后从记录的标记ID开始
    询问第二个集合中的工人，直到碰到第一个空闲工人为止，记录这个工人的ID做为标记ID。
---------回复--------------
给的条件：1、按ZZ的ID号安排任务；
          2、GG分配任务，记住了上次的ZZ的ID号，然后分配（也得问有没有活）；
          2、ZZ领到GG的任务，GG就不管了；
          3、MM要问过后，工作开始。
          4、ZZ不说谎！

需要调整：
          GG分配给谁任务，要MM知道,MM只是去问分配了新工作的ZZ，让他们开始耕地。



---------回复--------------
考察MBA管理方法？用金字塔算法
---------回复--------------
每次都问一下工人  "厂长今天找你了吗(找你分配任务了吗)", 如果说没有(这个人)那么后面的就不要问了. 肯定都没有任务啦; 
我的一个想法  , 碰到这样的厂长,工号靠前的工人真可怜.
---------回复--------------
这么简单的问题。。。

前提条件MM只知道有10000个工人，按顺序分配工作。每天任务数和任务的长度什么的都不知道。
第一天MM从第一个工人哪里开始问：有活干没？一直问到第n个，发现他没有活干。然后把这个n值记录下来。
第二天MM从第n个人开始问：有活干没？可能得到下面三种回答
1、有活干，几天前就安排好了。这种人直接无视，下一个。。。
2、有活干，今天刚安排的。MM:“赶紧干活去，下一个”
3、没有活干。记录下这个人的编号n，今天的训话到此为止。
......
以后每天都像第二天那么干

备注：有可能10000个工人每个人都安排了活，这个时候发现问了10000个人之后要记得休息。。。
---------回复--------------
上面给出的算法有点小问题，第二天记录的n不应当是没有活干的人，而是最后一个今天刚被安排新任务的人的下一个人的编号
---------回复--------------
谢谢大家的讨论，已结帖。