北方大学 ACM 多校训练赛 第五场(D. 节操大师 - 二分)

Description

MK和他的小伙伴们（共n人，且保证n为2的正整数幂）想要比试一下谁更有节操，于是他们组织了一场节操淘汰赛。他们的比赛规则简单而暴力：两人的节操正面相撞，碎的一方出局，而没碎的一方晋级（脑补一下端午节的碰鸡蛋游戏>_<）。最后经过数轮淘汰决出冠军“节操大师”。

通过理性的研究，你测算出他们的节操值分别为1,2,…,n，我们不妨称这个值为“硬度”吧。同时你又测出了一个节操常数k：当两个硬度相差超过k的节操相撞时，硬度小的节操必碎；而当两个硬度相差不超过k的节操相撞时，由于现场操作的不确定因素，两个节操都有碎的可能（当然我们假设不会出现两边都碎的情况囧）。

显然，节操值较低的人也许没有任何可能得到冠军。下面就请你预测，这次比赛的冠军“节操大师”的节操最小值为多少。

Input

输入只有一行，两个正整数n和k分别表示参赛人数和节操常数。

Output

输出一行，一个正整数，表示“节操大师”的节操最小值。

Source

Nankai UniversityFreshman Programming Contest 2015
样例输入

8 2

样例输出

3

二分答案，从后往前·推

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <functional>
#include <cstdlib>
#include <queue>
#include <stack>
#include<set>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])  
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair 
#define fi first
#define se second
#define vi vector<int> 
#define pi pair<int,int>
#define SI(a) ((a).size())
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
    while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
    return x*f;
} 
int n,k;
bool check(int x) {
    set<int> S;
    set<int>::iterator it;
    For(i,n) if (i!=x) S.insert(-i);S.insert(0);
    vi v; v.pb(-x);
    int i=0;
    for(int l=1;l<=n/2;l<<=1) {
        int now=SI(v);
        For(j,l) {
            int p=v[i++];
            it=S.lower_bound(p-k); 
            int q=*it;
            if (!q) return 0;
            S.erase(q);
            v.pb(q);v.pb(p);
        }
    }
    return 1;
}
int main() {

    {
        n=read(),k=read();
        int l=1,r=n,ans=-1;
        while(l<=r) {
            int m=(l+r)/2;
            if (check(m)) ans=m,r=m-1;
            else l=m+1;
        }

        printf("%d\n",ans);
    }

    return 0;
}