2003集训队100道讨论题雷环中0051解题报告

1、IOI2003中国国家集训队难题讨论活动0051 解题报告重庆外语学校 雷环中【题目大意】N个人通过潜水的方法过河，但只有一个氧气瓶，不够两人以上同时使用。两个学生一起潜水时，其速度与两人中慢者相同。有M对学生不喜欢对方，不能一起潜水。找出一种全部过河且总时间最少的方案。N，M6000 。【解决情况】对于原题笔者并不知道该如何解决。在本次讨论活动中，在M=0解决的基础上，大家提出了不少猜想，但遗憾的是最终未能解决M0的情况。在附录论文的基础上，笔者简单地写一个关于M=0的解题报告，希望起到抛砖引玉的作用。如本文有阐述不清的地方，请参见附录论文。M=0时算法的时间复杂程度为O(NlogN)，包括

2、O(NlogN)的排序和O(N)的核心算法。空间复杂度为O(N)。【算法梗概】贪心。每次根据未过河的人中最快的两人和最慢的两人的速度关系构造方案【讨论收获与感谢】特别感谢何林同学推荐论文。【正文】本文要谈的主要内容在附录论文中已用非常通俗易懂的语言详细准确的予以了阐述，本文也没有必要再罗嗦一遍，所以只简单扼要的谈一谈，再略作补充。先考察简单情况。当N=4，M=0时，如四人A，B，C，D过河时间分为1、2、5、8，我们可以迅速得到最优方案：AB2 (箭头右边的数为时间) A1CD8 B2AB2根据上述方案，我们可得一个不成熟的策略：应该充分利用A，B转移氧气瓶。然后我们再来粗略的考虑这种策略的必

3、要性。A的运用似乎是必要的(注意我们这里使用似乎，虽然比较显然，但还未经证明)，因为用A比用任何其他的人都省。B的运用是必要的吗？或许不是。因为我们前面提到过，用A比B省。然而我们为什么要用B而不用A？因为如果不如此，则方案应该是：AB2 A1A C5 A1AD8从总时间上看就亏了。因为2+1+8+2+22+1+5+1+8，最根本的原因是后方案中A一个人“忙不过来”。去掉相同的移动AB2和A1，不等式变为8225+1+8。这就是导致前方案更优的原因。更进一步，我们发现，D总是要过河的，而D不论与谁一起过，花的时间都是8，在不等式两边都减去8，就得到：2+251 。这是非常重要的结论，让我们来看

4、这个等式的意义：2*B的时间j)Y1又要和某人M一起到彼岸去，而第n+j+1步是“Y2回此岸来”，那么我们把第n+j步改为“A和M一起到彼岸”去，而把第n+k+1步改为“A回此岸来”。这样修改后的步骤消耗的时间也要比原先的少。如果Y2=Y自己，那么此后修改前后两种情况的局面就一样了。否则在执行第n+k+1步后，原先的局面和修改过后的局面的唯一差别在于前一种是Y2在此岸Y在彼岸，而后一种恰好相反。这样我们有序列Y1，Y2，依次修改下去，每次修改后消耗的总时间不会多于原先所需的，但是总会有一刻某个Yt和Y相同，结束这串修改。这样我们就得到了修改后的最佳方案，它的第n步也是符合结论六的要求的。这和我

5、们的反证假设矛盾，和结论三的证明方式相同，我们证明了结论六。接下来我们可以证明我们开始的猜想：结论七：一定有这样一种符合结论二六的最佳方案，在这个方案里，所有从彼岸到此岸的移动中，回来的人只能是所有人中最快的或者次快的。我们依然用变分法证明如下：假设结论七是错的，所有满足结论二六的最佳方案中，都必须至少有一次需要一个跑得不是最快或次快的人回来，那么我们选取一个这样的事情发生得最晚的最佳方案。假设在第n步，C从彼岸跑回了此岸，但他不是跑得最快或次快的人。设A和B分别是跑得最快和次快的人。因为第n步C跑回了此岸，所以之前定有一步，C从此岸到达彼岸，且根据结论六，那一步一定是A和C同行，我们假设此步

6、为第n-i步。又根据结论三，接下去一步是A回到此岸。在第n-i步和第n步间，无C的移动。考虑第n-1步：根据结论五，此步必定有两人从此岸移动到彼岸；这两人中没有A或B，否则第n步回此岸来的就该是比较快的A或B。同时显然，把第n-i步和第n-i+1步移到第n-1步前，方案仍旧可以合理进行。修改后的方案（原来第n-i步前的步骤加上原来第n-i+1和第n步间的步骤）第n-3步：A C （原来第n-i步）第n-2步：A （原来第n-i+1步）第n-1步：Y Z （Y和Z未知，但非A、B或C）第n步：C 我们用B代替C修改这4步的方案，得到的方案不但直到第n步还符合结论七，且所需时间比原方案短，明显违反

7、了假设，矛盾。也就是说，满足结论七的最佳方案是存在的。证毕。最后我们来分析每个人的过河方式。假设A为最快，B为次快，而Z是任意一个其他人。根据结论七，他只过一次河，就再不回来。考虑和他同行的另一位人，这里有两种可能性：另一位人还会回到此岸来。根据结论六，另一位一定是A。所以Z过河的模式是“由A护送到对岸，A返回”，称作“模式一”。另一位人也不回来了。假设这两人过河是在第n步。如方案中还有第n+1步，那么这另一个人就不是A。根据结论七，第n+1步应是A或者B回到此岸。但是根据结论四，我们知道第n步时A在此岸，所以第n+1步只能是B回来。但B在彼岸说明第n步前已有一步使B过河。根据结论六和结论三，

8、那一步定是与A同行，然后A回来。类似结论七的证明中我们的整体后移方法，我们可写出变换后Z的过河模式（设另一位人是Y，不同于A、B）：第n-2步：A B 第n-1步：A 第n步：Y Z 第n+1步：B 这个模式是“由A和B间接护送到对岸，A和B先后返回”，称作“模式二”。于是我们可以得到结论八：一定有这样一种符合结论二七的最佳方案，在这个方案里，所有除了最快和次快的人都以上面两个模式过桥，并且再不回来。最后让我们来考察最慢(Z)和次慢(Y)的人是如何过河的。先给出结论：结论九：所有符合结论八的最佳方案中，最慢两人过桥的模式必须相同，而且如果使用的都是模式二，那么他们一定在一起过河。证明如下： （

9、特别地，无论他们以何模式过河，我们总可在开始4步里将他们移动到彼岸）假设Z以模式一过河，但是Y却以模式二过河（步骤旁为此步所需时间）A Y yA aA B bA aX Z z（X是不为A或B的人）B bA X xA a A B bA aY Z zB b 把X和Y对换把X和Z对换A X xA aA B bA aZ Y zB bA Z z A Y yA aA B bA aX Z z（X是不为A或B的人）B bA X xA a A B bA aY Z zB b 把X和Y对换把X和Z对换A X xA aA B bA aZ Y zB bA Z z A aA B b A aX Y y （X是不为A或B的人）B b A B bA aW Y y（W是不为A或B的人）B bA B bA aX Z z（X是不为A或B的人）B b A B bA aW X A B bA aW Y y（W是不为A或B的人）B bA B bA aX Z z（X是不为A或B的人）B b A B bA aW X tB bA B bA aY Z zB b 把X和Y对换其中t是w和x中较大的一个。修改后的方案比原先的优，和原先的“最佳方案”假定矛盾。这就完全证明了结论九。至此，本算法正确性的证明完成。通过上面的九个结论，我们很自然的就得出了 HYPERLINK l 算法 最开始给出的算法。值得一提的是，证明中先后三次用