蓝桥杯酒店安排

2025/1/19 9:58:58 来源：https://blog.csdn.net/makeke123456/article/details/145089627 浏览: 次关键词：蓝桥杯酒店安排

问题概述

解题思路

这个问题可以通过排序和滑动窗口的方法来解决。首先，我们需要对酒店的位置进行排序，然后通过滑动窗口来找到最小最大距离。

步骤一：排序

对酒店位置数组A进行排序，以便我们可以按照顺序考虑酒店。

步骤二：滑动窗口

使用滑动窗口的方法，窗口的大小固定为M（即同学的数量）。窗口的起始位置从0开始，逐步向右移动，直到窗口的起始位置达到N−M。

步骤三：计算最大距离

对于每个窗口，计算窗口内任意两个酒店之间的最大距离。这个最大距离可以通过计算窗口起始位置和结束位置的酒店位置差来得到。

步骤四：更新最小最大距离

在遍历所有可能的窗口后，记录并输出所有窗口中的最大距离的最小值。

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>using namespace std;int main() {int N, M;cin >> N >> M;vector<int> A(N);for (int i = 0; i < N; ++i) {cin >> A[i];}// 对酒店位置进行排序sort(A.begin(), A.end());// 初始化最小最大距离为最大可能值int minMaxDistance = INT_MAX;// 使用滑动窗口找到最小最大距离for (int i = 0; i <= N - M; ++i) {// 计算当前窗口的最大距离int maxDistance = abs(A[i + M - 1] - A[i]);// 更新最小最大距离minMaxDistance = min(minMaxDistance, maxDistance);}// 输出最小最大距离cout << minMaxDistance << endl;return 0;
}