线上的点

线上的点

时间： 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;
}

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