问题描述

第十六届蓝桥杯比赛太火爆了，赛场周围的酒店早早地就被抢订一空，剩下的房间寥寥无几。作为蓝桥学院的指导老师，小蓝为此头疼不已，因为他需要将同学们分配到不同的酒店去入住。

本次比赛中，小蓝带领了 MM 名同学参赛。考场周围仅剩下 NN 家酒店有空房，每家酒店的位置用 AiAi​ 表示。酒店 ii 和酒店 jj 之间的距离为 ∣Ai−Aj∣∣Ai​−Aj​∣。

每位同学将在其中一家酒店入住，每家酒店只容纳一名同学。由于比赛第二天时间紧迫，小蓝希望同学们早早集合赶往考场。集合时间取决于任意两名同学所住酒店之间的最大距离。现在小蓝想知道这个最大距离可能的最小值是多少。

作为同学中的一员，希望你能帮助指导老师小蓝解决这个问题。

输入格式

第一行输入两个整数 N,M(1≤M≤N≤105)N,M(1≤M≤N≤105) 表示酒店的数量和同学的数量。

第二行输入 NN 个整数 A1,A2,A3,⋯AN(1≤Ai≤109)A1​,A2​,A3​,⋯AN​(1≤Ai​≤109) 表示每家酒店的位置。

输出格式

输出一个整数表示答案。

样例输入

5 3
3 1 6 4 5 

样例输出

2

样例说明

当 33 位同学入住第 1,4,51,4,5 号酒店时为其中一种最优情况，答案为 22。

运行限制

语言	最大运行时间	最大运行内存
C++	1s	512M
C	1s	512M
Java	2s	512M
Python3	3s	512M
PyPy3	3s	512M
Go	3s	512M
JavaScript	3s	512M

总通过次数: 1706  |  总提交次数: 2351  |  通过率: 72.6%

难度: 中等   标签: 思维, 排序

算法思路：排序 + 滑动窗口

这个问题本质是​​最小化任意两名同学之间的最大酒店距离​​。通过以下步骤高效解决：

1. ​​排序​​：

   • 酒店位置无序时，任意两点距离计算复杂。
   • 对酒店位置升序排序后，最大距离 = 最右侧酒店位置 - 最左侧酒店位置（因数组有序）。

2. ​​滑动窗口​​：

   • 窗口大小 = 同学数 M，在排序后的数组上滑动。
   • ​​关键性质​​：连续 M 个酒店的首尾距离（窗口最右值 - 最左值）即该窗口内任意两点最大距离。
   • ​​目标​​：找到所有窗口中最小首尾距离。

3. ​​算法正确性证明​​：

   • 非连续选择会扩大首尾距离（如图1），连续窗口的解一定 ≤ 非连续解。
   • 因此只需检查所有连续 M 个酒店的窗口。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;
    vector<long long> hotels(N);
    for (int i = 0; i < N; i++) {
        cin >> hotels[i];
    }

    // 排序：使酒店位置有序
    sort(hotels.begin(), hotels.end());

    // 特殊情况：只有1名同学，最大距离为0
    if (M == 1) {
        cout << 0 << endl;
        return 0;
    }

    long long min_max_distance = LLONG_MAX;
    // 滑动窗口：窗口大小为M
    for (int i = 0; i <= N - M; i++) {
        // 计算当前窗口的首尾距离
        long long distance = hotels[i + M - 1] - hotels[i];
        min_max_distance = min(min_max_distance, distance);
    }

    cout << min_max_distance << endl;
    return 0;
}

代码解析

1. ​​输入处理​​

   • 使用 ios::sync_with_stdio(false) 和 cin.tie(0) 加速输入输出。
   • 用 vector<long long> 存储酒店位置（避免 109 溢出）。

2. ​​排序​​

   • sort(hotels.begin(), hotels.end()) 将酒店位置升序排列，使后续计算高效。

3. ​​边界处理​​

   • 当 M=1 时直接返回0（无需计算）。

4. ​​滑动窗口核心逻辑​​

   • 遍历每个起始位置 i（0 到 N-M）。
   • 计算窗口内首尾距离：hotels[i+M-1] - hotels[i]。
   • 更新全局最小值 min_max_distance。

5. ​​输出​​

   • 最终结果即所有窗口中最小的首尾距离。

实例验证

​​输入样例​​：

5 3
3 1 6 4 5

​​执行流程​​：

1. ​​排序后数组​​：[1, 3, 4, 5, 6]
2. ​​滑动窗口过程​​：
   • 窗口 [1, 3, 4] → 距离 = 4-1=3
   • 窗口 [3, 4, 5] → 距离 = 5-3=2
   • 窗口 [4, 5, 6] → 距离 = 6-4=2
3. ​​输出结果​​：2（与样例一致）

测试点设计

​​测试场景​​	输入样例	预期输出	验证要点
最小规模（N=2, M=2）	2 2\n1 2	1	基础功能
M=1	5 1\n3 1 6 4 5	0	边界处理
M=N（全选酒店）	4 4\n1 10 100 1000	999	最大窗口距离计算
重复位置	3 2\n5 5 5	0	距离为0的情况
递增序列	5 3\n1 2 3 4 5	2	连续窗口最小距离
大规模数据	105 个酒店，M=104	首尾距离	时间效率（<1s）

优化建议

1. ​​算法优化​​

   • 当前时间复杂度 O(NlogN)（主要来自排序），已是最优解。
   • 滑动窗口部分 O(N) 无法优化。

2. ​​二分答案改进​​

   • 若问题约束更强（如 N≥107），可用二分答案：
     • 步骤1：在 [0,max_distance] 二分搜索最小可行距离 D。
     • 步骤2：检查函数 check(D) 能否选 M 个酒店，使任意两点距离 ≤D。
   • 时间复杂度 O(Nlog(max_distance))，但代码更复杂。

3. ​​工程优化​​

   • 输入输出加速（代码已实现）。
   • 用 long long 避免大数溢出。
   • 循环内避免不必要的函数调用。

正确性证明

​​反证法​​：假设存在非连续选择方案 S，其最大距离 DS​ 小于滑动窗口得到的结果 DW​。

• 设 S 中最左酒店位置 L，最右位置 R（R−L=DS​）。
• 在排序数组中，L 和 R 之间至少包含 M 个连续酒店（含 L 和 R）。
• 滑动窗口覆盖 [L,R] 时，其首尾距离 ≤R−L=DS​，与 DS​<DW​ 矛盾。
  ∴ 滑动窗口的解一定是最优解。

此方法高效解决了最小化最大距离问题，核心在于排序后连续窗口的数学性质。