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); }
Join the discussion