[问题描述]
有N头奶牛（N是2K），都是网球高手，每头奶牛都有一个BTP排名（恰好为1—N）。下周将要进行一场淘汰赛，N头奶牛分成N/2组，每组两头奶牛比赛，决出N/2位胜者；N/2位胜者继而分成N/4组比赛……直至剩下一头牛是冠军。
比赛既要讲求实力，又要考虑到运气。如果两头奶牛的BTP排名相差大于给定整数K，则排名靠前的奶牛总是赢排名靠后的；否则，双方都有可能获胜。现在观众们想知道，哪头奶牛是所有可能成为冠军的牛中排名最后的，并要求你列举出一个可能的比赛安排使该奶牛获胜。（限制N≤65536）
[分析]
由于N很大，我们猜想可以通过贪心方法解决。
我们希望排名靠前的选手总是“爆冷”输给排名靠后的选手。于是我们让1输给K+1、2输给K+2……每一轮中每一局总是选择未比赛的排名最前的选手，输给一个排名最靠后的选手（如果有的话）。
但我们很容易找到反例，例如：N=8,
K=2，由上述贪心方法我们得到对阵方式结果为4，见图BTP-1（其中XàY表示X战胜Y）。
图BTP-1
图BTP-2
但最优解为6，见图BTP-2。究其原因，因为我们不知道最优解是多少，所以我们是在盲目地贪心。事实上，最优解的6在第一轮就被我们淘汰了，当然就得不到最优解喽！
要想知道最优解？枚举！同时考虑到一个很显然的结论——如果排名为X的选手最终获胜，那么排名在X前的选手也可以获胜。
显然归显然，证明它我们还需要动一点小脑筋。假设排名X的选手最终获胜，我们通过对该对战方式的局部修改，构造出一种新的对战方式使任意排名Y<X的选手获胜：在X最终获胜的对战方式中，假设Y是被Z击败。如果Z≠X，由X>Y，可知Z一定也能击败X，且同一轮及此后X所击败的选手都能被Y击败，所以我们只需要在此轮让Z击败X，并把之后所有对战中的X都改成Y即可；如果Z=X，由X>Y，我们就让Y击败X，同样把之后对战中的X都改成Y，则最后获胜的也是Y。
因此，我们就可以用二分枚举最终获胜的X，大大提高了算法效率。
现在的问题是，如果我们知道最终获胜的是X，我们能否很快构造出一种对战方式或是证明不存在吗？可以，我们仍旧使用贪心，不过因为我们知道最终谁获胜，所以我们采用倒推。
每一轮，我们都让已有选手去战胜一个排名最靠前的还未出现的选手，由该方法产生的对战方式就如图BTP-2所描述那样。至于最靠前的未出现选手如何找，我们可以采用静态排序二叉树实现，这里不再展开，读者可以自己考虑。
可以证明这样贪心是正确的（证明方法同前面的证明类似，这里也不再重复）。整个问题可以在O(Nlog2N)时间完成。
[小结]
对于这类需要二分枚举的问题，其实算法的根本是在一个隐含的退化了的有序序列中进行二分查找，只是这个序列仅含有0和1两种值。上例中当X<Ans，A[X]=0；当X≥Ans，A[X]=1。而我们所寻找的就是这两种值的分界点。有了分界点，就有了最优值，也就有了原问题的解。