51Nod－1420－数袋鼠好有趣

ACM模版

描述

题解

Water!!!没想到这都是四级题~~~这让人情何以堪。

直接排序，二分查找一次，然后贪心即可。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int MAXN = 5e5;

int si[MAXN];

int bs(int l, int h, int v)
{
    int m;
    while (l < h)
    {
        m = (l + h) >> 1;
        if (si[m] < v)
        {
            l = m + 1;
        }
        else
        {
            h = m;
        }
    }
    return l;
}

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", si + i);
    }
    sort(si, si + n);
    int big = bs(0, n, 2 * si[0]);
    int res = 0;

    for (int i = 0; i < n / 2; i++)
    {
        while (si[big] < 2 * si[i] && big < n)
        {
            big++;
        }
        if (big < n)
        {
            big++;
            res++;
        }
    }

    cout << n - res << '\n';
    return 0;
}