题目大意
给定一个长度为 \(n\) 序列 \(a\),从中选取 \(m\) 个,满足对任意的 \(1 \leq i, j \leq m\),都有 \(|b_i - b_j| \leq \varepsilon\),其中,\(b\) 是选出来的 \(m\) 个数。
求最小的 \(\varepsilon\)。
解题思路
满足 \(|b_i - b_j| \leq \varepsilon\) 其实就是满足从 \(b\) 中任意选取两个数,这两个数的差不能大于 \(\varepsilon\),也就是说,\(\varepsilon\) 要大于或等于这两个数的差的最大值;题目中说要求 \(\varepsilon\) 为最小值,也就是从 \(b\) 中,找出最大的数和最小的数,它们的差其实就是 \(\varepsilon\)。
首先可以排个序,保证 \(a\) 单调不降,因为 \(a\) 有可能不是单调不降的序列;这样也使 \(m\) 个数是连续的。
为了使 \(\varepsilon\) 最小,就要使 \(b\) 中最大值与最小值最接近,要使 \(b\) 中最大值与最小值最接近,其实就是找排序后 \(a\) 中相下标相距 \(m\) 的两个数的差值最小,他们的差就是 \(\varepsilon\)。
要找排序后 \(a\) 中差值最小并且下标相距 \(m\) 的两个数,可以从 \(1\) 枚举到 \(n-m+1\)(因为要枚举 \(m\) 个数中的最小值,通过最小值找出最大值,所以 \(n-m+1\) 再往后的就不用重复枚举了),每次找 \(m\) 个数中最小的;用 \(a_{i+m-1}-a_i\)(\(a_{i+m-1}\) 与 \(a_i\) 的下标相距 \(m\)),求的是当 \(a_i\) 为 \(m\) 个数中最小的数的时候,\(m\) 个数中最大的数减 \(a_i\) 的差是多少;要取最小的差,所以要取每次 \(a_{i+m-1}-a_i\) 要与之前的最小差取最小值,即:
ans=min(ans,a[i+m-1]-a[i]);
注意要给 \(ans\) 赋一个极大值,不然答案会永远为 \(0\)。
代码
#include <bits/stdc++.h>
#define ri register int
using namespace std;
int n,m,a[100005],ans=INT_MAX; //赋极大值
int main(){
scanf("%d%d",&n,&m);
for(ri i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n); //排序
for(ri i=1;i<=n-m+1;i++)
ans=min(ans,a[i+m-1]-a[i]); //求排序后 a 中差值最小并且下标相距 m 的两个数的差的最小值
printf("%d",ans);
return 0;
}
标签:varepsilon,题解,yLOI2023,最小,个数,leq,最小值,P9064,ans
From: https://www.cnblogs.com/zzyblog0619/p/17138624.html