新手启示者
5167 最值之差
经验值：1200 时间限制：1000毫秒
题目描述 Description
输入n个数，要使最大值与最小值之差小于等于d，最少应该删除几个数。
输入描述 Input Description
第一行2个数，n和d表示一共n个数，最值之差最大为d
第二行n个数
输出描述 Output Description
最少应该删除的数字的数量
样例输入 Sample Input
3 1 2 1 4
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
n∈[1,100],d∈[0,100],每个数∈[1,100]
代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,d,a[105];
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
int l=1,r=2,minn=0x3f3f3f3f;
while(r<=n){
if(a[r]-a[l]<=d){
minn=min(minn,r-l);
}
r++;
l++;
}
cout<<minn;
return 0;
}
WA0分
中级启示者
核心：
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
int j=1;
for(int i=1;i<=n;i++){
while(j<=n&&a[j]-a[i]<=k) j++;
ans=min(ans,n-(j-i));
}
cout<<ans;
望采纳
李显晨在2021-07-11 20:00:32追加了内容
用这代码两题都能过，数组大一点就行
资深天翼
同上
资深守护
@袁宇泽
int check(int i){
int l=1,r=n-i;
int maxn=0x3f3f3f3f;
while(r<=n){
maxn=min(maxn,a[r]-a[l]);
l++;
r++;
}
if(maxn<=k) return true;
return false;
}
资深光能
你问李显晨，他知道
荣光峰在2021-07-11 19:59:30追加了内容
而且他二也写出来了
中级守护
定义 n,d,a[105];
定义 cnt,ans=101;
输入n和d
for循环(定义int i=1;i<=n;i++){
输入a[i];
}
for循环(定义int i=1;i<=n;i++){
for循环(定义int j=1;j<=n;j++){
如果(a[j]<a[i]||a[j]>a[i]+d){
cnt++;
}
}
ans=min(ans,cnt);
cnt=0;
}
资深守护
用二分：
int i=0,j=n;
while(i<j){
int mid=(i+j)/2;
if(check(mid)) j=mid;
else i=mid+1;
}
cout<<i;
check判断是否可以删除mid个数
修练者
谢谢
中级天翼
循环(定义 i=1;i<=n;i++)
输入>>a[i];
排(a+1,a+1+n);
定义 l=1;
循环(定义 r=1;r<=n;r++){
循环(l<=n&&a[l]-a[r]<=m){
l++;
minn=min(minn,n-(l-r));
}
}
输出<<minn;
