C++问题，简单，但不会，求解！

Question

在一个直线走廊上放着n张床，走廊的最左边是入口，我们用Di表示第i张床到入口的距离。

今天小核桃收留了m个人（m≤n），需要从n张床中选出m张床分配给这m个人睡（一个人睡一张床）。

但是这m个人晚上都会打呼噜，为了尽可能地避免大家晚上被别人的呼声吵到，小核桃希望找到一种分配方式，使得分配的床位两两之间的最小距离尽可能地大。

请你帮忙计算这个最大距离，使得存在一种分配方式能让任意两个人的床位的距离都不小于这个最大距离。

Answer 1

这个问题可以通过二分查找和贪心算法来解决。

首先，我们需要对床位的距离进行排序。假设床位的距离数组为distances，其中distances[i]表示第i张床到入口的距离。我们可以使用快速排序或其他排序算法对distances进行排序。

然后，我们可以定义一个函数check()来检查是否存在一种分配方式，使得任意两个人的床位距离都不小于某个给定的距离mid。在check()函数中，我们可以使用贪心算法来尽可能地安排床位，使得任意两个人的床位距离都不小于mid。

具体的实现步骤如下：

对床位距离数组distances进行排序。
使用二分查找，在最小距离0和最大距离distances[n-1]之间确定一个中间距离mid。
在check()函数中，从位置0开始遍历床位距离数组。每次选择当前位置的床位，并计数已经分配的床位数。当已经分配的床位数等于要分配的人数m时，计算当前的床位距离是否大于等于mid。如果是，则返回真；否则，继续遍历床位距离数组。如果遍历完整个数组时仍然没有找到满足条件的分配方式，则返回假。
在二分查找中，不断调整最小距离和最大距离，直到最小距离等于最大距离为止。此时，最小距离即为所求的最大距离。

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

bool check(vector<int>& distances, int mid, int m) {
    int count = 1;
    int cur_distance = 0;
    
    for (int i = 1; i < distances.size(); i++) {
        if (distances[i] - distances[cur_distance] >= mid) {
            count++;
            cur_distance = i;
        }
        
        if (count == m) {
            return true;
        }
    }
    
    return false;
}

int max_distance(vector<int>& distances, int m) {
    sort(distances.begin(), distances.end());
    
    int left = 0;
    int right = distances.back();
    int result = 0;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (check(distances, mid, m)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    vector<int> distances = {3, 5, 8, 10, 14};
    int m = 3;
    
    int max_dist = max_distance(distances, m);
    cout << max_dist << endl;
    
    return 0;
}

```c++

```