题解

这道题目涉及到一个$2^n$个选手的淘汰赛，每个选手有一个唯一的排名。每一轮比赛中，排名差距小于或等于$k$的选手可以相互击败，而排名差距超过$k$的比赛则由排名靠前的选手获胜。我们的目标是找出最差的那个有可能最终获胜的选手的排名。

解题思路

1. 问题建模：

   • 我们有$2^n$个选手，每个选手有一个确定的排名，且排名没有重复。
   • 每一轮比赛中，如果两个选手的排名差距大于$k$，排名较高的选手一定会获胜；如果排名差距小于或等于$k$，则比赛结果不可预测。

2. 二分查找：

   • 通过二分查找来确定能最终获胜的最差排名。最差排名是指在比赛中有可能经过所有轮次最终获胜的排名。
   • 我们需要倒着模拟比赛过程，假设某个排名能最终获胜，检查这个假设是否成立。

3. 模拟比赛：

   • 对于每一轮比赛，我们会尝试模拟比赛过程：从当前排名的选手出发，找到它能够打败的所有最强对手，直到最终确认其能否进入下一轮。
   • 模拟过程中使用动态规划记录哪些选手能够进入下一轮。

4. 实现细节：

   • 使用一个布尔数组 v 来记录当前选手能否进入下一轮。
   • 每轮比赛中，若某个选手能够击败其范围内的对手，则将其标记为能进入下一轮。

二分查找的核心操作

1. check(x)：判断排名为$x$的选手能否最终获胜。该函数通过模拟比赛过程来验证排名为$x$的选手是否有可能通过所有轮次获得最终的胜利。

2. 二分查找：通过调整最小和最大可能排名范围，最终找到最差能获胜的排名。

代码解析

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int n, k, c;  // n: 选手数量，k: 影响胜负的排名差，c: 总共的比赛轮数
bool v[2][5005];  // 用来标记某一轮是否能进入下一轮
int hh = 1;  // 当前轮数

// check函数用于判断排名为x的选手是否有可能最终获胜
bool check(int x) {
    memset(v, 0, sizeof(v));  // 重置布尔数组
    hh = n;
    v[1][x] = true;  // 假设排名x的选手能进入第一轮

    for (int i = 1; i <= c; i++) {
        for (int j = 1; j <= n; j++) {
            v[(i + 1) % 2][j] = v[i % 2][j];  // 复制上一轮的结果
        }

        // 模拟比赛
        for (int j = 1; j <= n; j++) {
            if (v[i % 2][j]) {
                bool flag = false;
                // 寻找能打败的对手
                for (int u = max(1, j - k); u < j; u++) {
                    if (!v[(i + 1) % 2][u]) {
                        flag = true;
                        v[(i + 1) % 2][u] = true;
                        break;
                    }
                }
                // 如果没有找到，可以击败的对手，则尝试从右侧找
                if (!flag) {
                    for (int u = j + 1; u <= n; u++) {
                        if (!v[(i + 1) % 2][u]) {
                            flag = true;
                            v[(i + 1) % 2][u] = true;
                            break;
                        }
                    }
                }
                // 如果都找不到可以击败的对手，则返回false
                if (!flag) return false;
            }
        }
    }
    return true;  // 如果所有轮次都能胜利，则返回true
}

// 主函数，使用二分查找找出最差能够获胜的选手排名
void work() {
    int l = 1, r = n, mid, ans = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            ans = mid;  // 如果mid能够获胜，尝试更大的排名
            l = mid + 1;
        } else {
            r = mid - 1;  // 否则尝试更小的排名
        }
    }
    printf("%d\n", ans);  // 输出最终的答案
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0;; i++) {
        if ((1 << i) == n) {
            c = i;
            break;
        }
    }
    work();  // 执行二分查找，找出最差获胜选手的排名
    return 0;
}

代码解析

1. check(x)：

   • 模拟从排名为x的选手开始，经过每一轮比赛，查看是否能够一直打败比自己排名差的选手，直到最后一轮。
   • 使用动态规划来保存哪些选手能在当前轮次进入下一轮。

2. work()：

   • 使用二分查找来找出最差的获胜排名。通过反复调用check(mid)来确定某个排名是否能够最终获胜。
   • 如果某个排名可以获胜，则尝试更高的排名，反之则尝试更低的排名。

复杂度分析

• 时间复杂度：

  • 每次二分查找的查找范围是$1 \leq x \leq n$，共进行了$\log n$次查询。
  • 每次查询需要模拟$n$个选手的比赛过程，最多需要进行$c$轮，每轮处理$O(n)$个选手。
  • 总的时间复杂度为$O(n \cdot c \cdot \log n)$。

• 空间复杂度：

  • 使用了$O(n)$的空间来存储每轮比赛的结果。

总结

通过二分查找和模拟比赛的方式，解决了在淘汰赛中，最差的能获得最终胜利的选手排名问题。这个解法利用了动态规划模拟比赛过程，同时通过二分查找优化了计算过程，确保了在较大规模的数据下能够高效解决问题。