NYOJ习题 删除元素（二分查找）

NYOJ练习题 删除元素（二分查找）

删除元素时间限制：1000 ms  |  内存限制：65535 KB

描述

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

输入

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

输出

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

样例输入

65 4 3 3 8 6

样例输出

1

解题思路：先对n个数从小到大排序，然后枚举删除一些元素后剩余集合中最小的数Min，二分求出原集合大于2*Min的数的个数，然后即可求的当前要删除的元素个数，比较取最优的即可。

#include<stdio.h>#include<algorithm>using namespace std;const int N = 1e5 + 10;int a[N];int Binary(int k, int n){    int l = k, r = n;    while(l < r)    {        int mid = (l + r) / 2;        if(a[mid] > 2*a[k])            r = mid;        else            l = mid + 1;    }    return  n - r;}int main(){    int n;    while(~scanf("%d",&n))    {        int i, j;        for(i = 0; i < n; i++)            scanf("%d",&a[i]);        sort(a,a+n);        int ans = 1<<30;        for(i = 0; i < n; i++)        {            int s = i;            s += Binary(i,n);            ans = min(ans,s);        }        printf("%d\n",ans);    }    return 0;}//先排序，然后枚举删除一些元素后剩余集合中最小的数Min//二分求原集合中大于2*Min的数的个数，进而即可求得当前要删除的元素个数//比较去最优的即可