P9064 [yLOI2023] 苦竹林 题解

· · 题解

题目要求从 a_1,a_2,...,a_n 中选出 m 个数字 b_1,b_2,...,b_m，使得任意两数之差的最大值最小化。

首先将 a 数组从小到大排序，对于一个有序序列，任意两数之差的最大值必定是最后一个数减去第一个数，而又容易证明选择连续的一段有序序列必定是最优的，那么只要枚举每一个 1 \leq i,i+m \leq n，计算 a_{i+m}-a_i 的最小值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100009;
ll n,m,b[100009];
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)  b[i]=read();
    sort(b+1,b+1+n);
    ll ans=0x3f3f3f3f3f3f3f3f;
    for(int i=m;i<=n;i++){
        ans=min(ans,b[i]-b[i-m+1]);
    }
    cout<<ans;
    return 0;
}