贪心好题(一)

ATP

题目大意:有N个运动员(N为2的幂次), 他们的能力值是一个排列, 一个运动员只可能打败能力值比他小不超过K的运动员, 问理论上可能夺得冠军的运动员能力值最大为多少?

解题报告

二分+贪心, 但是想不到…反着模拟每个运动员每次打败他能打败的最强运动员, 看能不能复原。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 5050;
int N, K;
bool vis[MAXN];
bool check (int a) {
    //printf("at:%d\n", a);
    memset(vis, 0, sizeof vis);
    vector<int> A, B;
    A.push_back(a);
    vis[a] = true;
    while(true) {
        if(A.size() == N) return true;
        B=A;
        for(int i = 0; i<A.size(); i++) {
            int j;
            for(j = max(A[i]-K, 1); j<=N; j++)
                if(!vis[j]) {vis[j] = true; B.push_back(j); break;}
            if(j>N) return false;
        }
        A.swap(B);
    }
}
int main () {
    scanf("%d%d", &N, &K);
    int lb = 1, rb = N, ans = 0;
    while(lb <= rb) {
        int mid = (lb+rb)>>1;
        if(check(mid)) lb = mid+1, ans = mid;
        else rb = mid-1;
    }
    printf("%d\n", ans);
}