设有m个野人，n个修道士,（m≤n）船上可坐c个人。
1. c=1，无解；
2. c=2，对较小的M,N有解，对于较大的M,N无解，比如m=n=4，c=2无解；
3. c=3，情况同上；
4. c>3，分情况讨论如下：
(1) m=n，
此时可以按照下面的方案设计（下面S表示野人savage，R表示修道士religious， B表示船boat, ||表示河）
方案一：
m S || (m-c)S || cS (m-c+1) S || (c-1) S (m-c+1)S || (c-1)S (m-c+2)S || (c-2)S
m R || => m R || => m R || => (m-c+1)R || (c-1)R => (m-c+2)R || (c-2)R
B || || B B || || B B ||
于是又回到了开始时候的情况，两岸的S,R相等且船在左岸，已经有c-2个S和c-2个R过了河。依次做下去，最终所有的人都会过河；
还有一种方案：
方案二：
mS || (m-[c/2])S || [c/2]S (m-[c/2]+1)S || ([c/2]-1)S
mR || => (m-[c/2])R || [c/2]R => (m-[c/2]+1)R || ([c/2]-1)R
B || || B B ||
最终也会到两岸S，R相等而船在左岸的情况，有[c/2]-1个S和R过了河。
当c为偶数时，方案一和方案二的过河速度是一样的；当c为奇数时，方案一要比方案二快。
当m=n时，一些特例需要考虑：
a. k≥m+n，让所有人一次全部过河；
b. k≥m, 用上面的方案一；
(2)n>m时，
①n=m+1，又分以下两种情况：
(a) c为偶数，方案如下：
方案三：
mS || (m-c)S || cS (m-c+1)S || (c-1)S (m-c+1)S || (c-1)S (m-c+1)S || (c-1)S
nR || => nR || => nR || => (n-c)R || cR => (n-c+1)R || (c-1)R
B || || B B || || B B ||
令m'=m-c+1,n'=n-c+1，则又重复了n'=m'+1的情况；
(b) c为奇数，设c=2h+1，显然a的方案三也可用，另外还有以下方案：
方案四
mS || (m-h)S || hS (m-h)S || hS
nR || => (n-h-1)R || (h+1)R => (n-h)R || hR
B || || B B ||
令m'=m-h,n'=n-h，又回到了n'=m'+1的情况。按照这个方案每次h个S和h+1个R过河，然后1个R回来。
当c为奇数的时候a,b两种方案的过河速度一样。
②n≥m+2时：
(a) c为奇数时，可以用n=m+1的情况b的方案四。
(b) c为偶数时，设c=2h，可以每单次过h-1个S，h+1个R，然后回来一个R，每双次过h个S，h个R，回来一个R.具体如下所示：
方案五：
mS || (m-h+1)S || (h-1)S (m-h+1)S || (h-1)S (m-2h+1)S || (2h-1)S (m-2h+1)S || (2h-1)S
nR || => (n-h-1)R || (h+1)R => (n-h)R || hR => (n-2h)R || 2hR => (n-2h+1)R || (2h-1)R
B || || B B || || B B ||
令m'=m-2h+1, n'=n-2h+1，重复上述过程。
算法设计的总思路是每次过河的人尽可能地多，回来的人尽可能地少，当n>m,c≥2的时候总是有解。
上述的算法已经说的很清楚了，程序你应该可以自己写出来吧。
这个问题是NOI复赛考过的题目，题目不难，但是要注意讨论全面。
|
本类阅读TOP10