1818:ATP

网址如下：

OpenJudge - 1818:ATP

刚刚开始我是想用分治做的，看这玩意涉及到了2^x我就想到了这玩意

结果正着解差点死掉，除了证明了当k * 3 > n的时候答案为n以外，一事无成

最后观摩了大佬的代码，发现可以假设答案，逆着来做

用到了二分法

代码如下：

#include<cstdio>
#include<algorithm>

const int maxn = 5000;
int n, k;

bool judge(int a) {
    bool vis[maxn]{}, fail;
    int val[maxn], cnt = 1, len = 1;
    vis[a] = true; val[0] = a;
    for( ; len < n; len *= 2)
        for(int i = 0; i < len; i++){
            fail = true;
            for(int j = std::max(0, val[i] - k); j <= n; j++)
                if(!vis[j]) {
                    fail = false;
                    vis[j] = true;
                    val[cnt++] = j;
                    break;
                }
            if(fail) return false;
        }
    return true;
}

int main() {
    scanf("%d%d", &n, &k);
    int l = 1, r = n + 1;
    while (r - l != 1) {
        int mid = (l + r) / 2;
        if(judge(mid)) l = mid;
        else r = mid;
    }
    printf("%d", l);

    return 0;
}

思路：

mid为假设的答案，如果mid可以，则l = mid，否则r = mid

其中l和r代表的是[l, r)的左闭右开区间

这些都是main函数的，应该很容易就看懂

最后是判断mid是否可以作为答案的内容：

从mid出发，找一个排名最小（或者说最高的）mid又可以打过的人，然后判mid赢

不难发现对于一个排名为val的人，他可以打赢[val - k, n]排名的人，我们从这里找是否有这样的人，如果有，则放进数组

现在数组有两个人，如果总决赛只剩下这两个人，理论上mid就可以胜出

如何让总决赛只剩下这两个人呢？

再给每一个人找一个人，让他们能打赢，且在半决赛的时候判这两个人赢就行了

以此类推

不难得出，找出的这个人，排名要尽可能的小（高），才有利于找到方案

且当找不到下一个人的时候，mid就无法作为答案