BZOJ 1034 [ZJOI2008] 泡泡堂 BNB

发布于 2017-05-02  167 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1034

题意:有两个队伍,都有 n 名选手,每个选手有一个战斗力,两两对战,胜者得 2 分,平得 1 分,设计两个方案分别使得 A 队分最高和最低。


读完题.. 肯定能想到田忌赛马.. 实际上,就是 n 匹马的田忌赛马...

我们从最下等马开始考虑... 若能战胜对方最下等马,显然直接赢掉它是最优策略... 但是若无法赢对方最小,则分情况考虑

若我方最大可以赢对方最大,则不需要送掉我方最小,直接用我发最大赢掉对方最大即可。

若不能,则放弃我方最小,去与对方最大对战。更加详细的证明引用自 这里

我的最小能否赢过敌方最小?[1]
是:赢过,迭代
否:我的最大能否赢过敌方最大?[2]
是:赢过,迭代
否:我方最小比拼对方最大,迭代。
让我们证明这个算法的正确性。当 [1] 成立时,最优性显然成立。当 [1] 不成立时,如我方最小输对方最小,正确性也是显然的。
在这里我们观察我方最小平敌方最小的情况,如进行比拼,收益为 1,而比拼敌方最大后,我方最大能赢过敌方最小则收益为 2,这种情况的唯一反例是我方最大能赢过敌方最大,在 [2] 中被叙述。

另外需要注意的是... 总分数一定是 2n,所以在计算第二种情况时即是 2n-B 队的最大收益

那么代码如下:

 


一个非常弱的准退役OIER