P9064 题解（2023 激励计划评分 7）

so_find_skind · 2023-02-14 18:10:39 · 题解

虽然题目描述有点多，但杂话一堆综合起来实际上就一句话：

从 n 个数里选出 m 个数，使得这 m 个数中最大数与最小数之差最小。

既然提到了最大数与最小数，就肯定要进行排序，此时 n 个数单调不减。

之后要使最大最小之差最小，必然需要是连续的 m 个数字才有可能，因为无间隔情况显然比有间隔情况更优。

code：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],ans=0x3f3f3f3f;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n-m+1;i++){
        ans=min(ans,a[i+m-1]-a[i]);
    }
    cout<<ans;
    return 0;
}