记录编号	124852	评测结果	AAAAAAAAAA
题目名称	1724.[USACO Dec02]奶牛职业网球赛	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2014-10-06 14:54:37	内存使用	5.38 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
const int SIZEN=65540;
int lg2(int x){
	int ans=-1;
	while(x) ans++,x>>=1;
	return ans;
}
int N,K,R;//R是回合数
int game[20][SIZEN];
bool vis[SIZEN]={0};
//game里:前一半存放胜者,后一半存放负者
bool check(int x){//让x赢得比赛
	game[0][1]=x;
	for(int i=1;i<=R;i++){
		int n=1<<i-1;//这一轮是n组比赛,选出n个人,即game[i-1]里的人
		memset(vis,0,sizeof(vis));
		for(int j=1;j<=n;j++) vis[game[i-1][j]]=true,game[i][j]=game[i-1][j];
		sort(game[i]+1,game[i]+1+n);
		int p=1;
		for(int j=1;j<=n;j++){//让game[i][j]战胜一个排名尽量靠前的人
			while(p<=N&&(vis[p]||p<game[i][j]-K)) p++;
			if(p==N+1) return false;
			//game[i][j]将战胜p
			vis[p]=true;
			game[i][j+n]=p;
		}
	}
	return true;
}
void work(void){
	int l=1,r=N;
	while(l<r){
		int mid=(l+r)/2;
		if(check(mid+1)) l=mid+1;
		else r=mid;
	}
	printf("%d\n",l);
}
int main(){
	freopen("btp.in","r",stdin);
	freopen("btp.out","w",stdout);
	scanf("%d%d",&N,&K);
	R=lg2(N);
	work();
	return 0;
}