nyoj 776 删除元素

删除元素

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

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

输入
多组测试数据,每组测试数据包含两行。
第一行一个整数n( n <= 10^5),序列中元素的个数。
第二行依次输入n个数a1,a2……an,(1 <= ai <= 10^9)以空格分开。
输出
输出占一行,至少要删除数的个数。
样例输入
6
5 4 3 3 8 6
样例输出
1
来源
普通方法超时
#include<stdio.h>
#include <algorithm>
using namespace std;
int a[100001];
int main()
{
    int t,i,j,k,max;
    while(scanf("%d",&t)==1)
    {
        for(i=0;i<t;i++)
            scanf("%d",&a[i]);
        sort(a,a+t);
        max=0;
        for(i=0;i<t;i++)
        {
            k=1;
            for(j=i+1;j<t;j++)
            {
                if(a[j]<=a[i]*2)
                k++;
            }
            if(k>max)
            max=k;
        }
        printf("%d
",t-max);
    }
    return 0;
}
View Code

二分已过:

#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;
    }
    printf("%d ",n-r);
    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
",ans);
    }
    return 0;
}
//先排序,然后枚举删除一些元素后剩余集合中最小的数Min
//二分求原集合中大于2*Min的数的个数,进而即可求得当前要删除的元素个数
//比较去最优的即可
View Code

原文地址:https://www.cnblogs.com/asd1234/p/3381587.html