【南开OJ2264】节操大师（贪心+二分+并查集/平衡树)

好久没更新了，今天就随便写一个吧

题目内容

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

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

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

(n≤131072, 保证n为2的正整数幂)

首先要二分答案，然后从结果考虑，最终假如是X决赛获胜，那么我们贪心地想，让X与他能获胜的节操值最大的人进行半决赛，这样可以达到最优的结果

如果那个人已经参与了比赛，就选第二大的，依次类推。

于是这个题就有了两种做法，一种是用并查集，一种是用平衡树（或者是set）

每次查询后利用并查集并点(logn)或者直接用set删点(logn)

最后的复杂度就是nlognlogn

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <set>

using namespace std;

const int maxn = ;

vector <int> V;

set<int> S;

int n, k;

bool ok(int u)

{

    S.clear();

    for(int i = ; i <= n; i++) S.insert((-i));

    V.clear();

    V.push_back(-u); S.erase(-u);

    while(V.size() != n)

    {

        int l = V.size();

        for(int i = ; i < l; i++)

        {

            int x = V[i];

            int y = *S.lower_bound(x-k);

            if(y == ) return false;

            V.push_back(y);

            S.erase(y);

        }

        //for(int i = 0; i < l; i++) printf("%d ", -V[i]);

        //cout<<endl;

    }

    return true;

}

int main()

{

    while(cin>>n>>k)

    {

        int l = , r = n, mid;

        while(l < r)

        {

            mid = (l+r)/;

            if(ok(mid)) r = mid;

            else l = mid+;

        }

        cout<<l<<endl;

    }

}