学步园

题意很简单，给一个长度为n的序列，问至少删除序列中多少个数，使得删除后的序列中的最大值<= 2*最小值

输入

多组测试数据，每组测试数据包含两行。
第一行一个整数n( n <= 10^5)，序列中元素的个数。
第二行依次输入n个数a1，a2……an，（1 <= ai <= 10^9）以空格分开。

输出

输出占一行，至少要删除数的个数。

样例输入

6
5 4 3 3 8 6

样例输出

1

来源

飘谊系列

上传者

PIAOYI

一个O(nlogn)算法，一个O(n)算法

#include<iostream>
#include<algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100010;

struct delNum {
    int n,ans;
    int str[MAXN];
    void init() {
        ans = -1;
    }

    void readNum() {
        for(int i=0; i<n; i++) {
            scanf("%d",&str[i]);
        }
    }

    void deal_nlogn(){//O(nlogn)的时间复杂度，随便调用哪个
        sort(str,str+n);
        for(int i = 0; i < n; i++) {
            int tmp = str[i]*2;
            if(tmp > str[n-1]) {tmp = n;}
            else tmp = binarySearch(tmp);
            ans = max(ans,tmp - i);
        }
    }

    void deal_n(){//O(n)的时间复杂度
        sort(str,str+n);
        for(int i = 0, k = 0; i < n; i++) {
            while(k < n && str[k] <= 2*str[i])k++;
            if(k-i>ans)ans = k-i;
        }
    }

    int binarySearch(int doubleNum) {
        int l = 0, r = n-1;
        while(l <= r) {
            int mid = (l+r)>>1;
            if(doubleNum == str[mid]) {
                while(str[++mid] == doubleNum);
                return mid;
            }
            if(str[mid] > doubleNum && str[mid-1] < doubleNum) {
                return mid;
            }
            if(str[mid] > doubleNum) {
                r = mid;
            } else {
                l = mid+1;
            }
        }
        return -1;
    }
}test;

int main() {
    //freopen("F:\\in.txt","r",stdin);
    while(~scanf("%d",&test.n)) {
        test.init();
        test.readNum();

        test.deal_nlogn();//test.deal_n();

        printf("%d\n",test.n - test.ans);
    }
    return 0;
}