P9064 [yLOI2023] 苦竹林

Algo_Sl_al · 2023-02-14 21:12:34 · 题解

题目传送门

题意简述

在 n 个数中选出 m 个数，使得这 m 个数中最大值减最小值的值最小。

思路简述

我们要让最大数与最小数的差尽可能小就要使得这些数尽量接近，容易想到使用排序然后枚举每一个 i \sim i+m-1 的区间，其中 1 \le i \le n-m+1 。对于每个区间，求出它的最大值减最小值的差，然后打擂台取最小值即可。

这样，我们就可以写出代码：

代码

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
    int n,m,ans=INT_MAX;//ans要赋值为一个极大的数，这里的INT_MAX就是int的最大值
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);//排序
    for(int i=1;i<=n-m+1;i++){
        ans=min(ans,a[i+m-1]-a[i]);//打擂台求最小值
    }
    cout<<ans;
}

AC记录