正经题解｜小明的魔力球

题目解析

差值越小的两个数距离越接近，如 与6最近的数为本身，其次是5和7。只需要从大到小排序，这样可以保证每个数之间距离最近，在遍历所有情况即可。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t,n,m;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++) cin >> a[i];
    sort(a,a+m,greater<int>());
    int ans = 0x3f3f3f3f;
    for(int i=0;i + n - 1 < m;i++) {
//        cout <<a[i] - a[i+n-1] << endl;
        ans = min(ans,a[i] - a[i+n-1]);
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

复杂度为 $O(n)$。