线上的点

时间: 1ms        内存:128M

描述:

有n个整数和一个整数d(1 ≤ n ≤ 100, 0 ≤ d ≤ 100) ,现在要使得这n个数中任意两个数的差值不大于d,问至少要删除几个数。

输入:

第一行:n,d 输入整数的个数以及n个整数之间的最大差值。
第二行:n个整数xi(1<=xi<=100)。

输出:

至少要删除的数的个数。

示例输入:

3 1
2 1 4

示例输出:

1

提示:

参考答案(内存最优[1120]):

#include<stdio.h>
#define max(x,y)(x>y?x:y)
int main()
{
    int n,m,t;
    int a[101];
    int i,j,ans=0,sum;
    scanf("%d%d",&n,&m);
     for(i=0;i<n;i++)
        scanf("%d",&a[i]);
     for(i=0;i<n;i++)
        for(j=0;j<n-1-i;j++)
     {
         if(a[j]>a[j+1])
         {
             t=a[j];
             a[j]=a[j+1];
             a[j+1]=t;
         }
     }
     for(i=0;i<n;i++)
     {
         sum=0;
         for(j=i;j<n;j++)
     {
         if(a[j]-a[i]<=m)
            sum++;
     }
     ans=max(ans,sum);
     }
        printf("%d\n",n-ans);
        return 0;
}

参考答案(时间最优[2]):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
    return a<b;
}
int main()
{
    int n,d,i,j,a[110];
    while(cin>>n>>d)
    {
        for(i=0; i<n; i++)
        {
            cin>>a[i];
        }
        sort(a,a+n,cmp);
        int cont=0;
        for(i=0;i<n;i++)
        {
            int ans=1;
            for(j=i+1;j<n;j++)
            {
                if(a[j]-a[i]>d)
                    break;
                ans++;
            }
            cont=max(cont,ans);
        }
        cout<<n-cont<<endl;
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。