第三部分：题目分析与标准代码

1. 算法思路

• 排序：首先将坐标数组 $X$ 从小到大排序，这是处理距离问题的基础。
• 判定函数 check(d)：
  • 假设最小间距是 $d$，我们能否选出 $M$ 个点？
  • 贪心策略：为了尽可能多放点，第一个点必须选（坐标最小的）。之后的点，只要距离上一个选中点的距离 $\ge d$，就立刻选中。
  • 如果最终选中的数量 $\ge M$，说明间距 $d$ 是可行的（甚至可能更大）。
  • 如果数量 $< M$，说明间距 $d$ 太大了，需要缩小。
• 二分答案：
  • 答案的范围在 $[0, 10^9]$ 之间（或者 X[N-1] - X[0]）。
  • 如果 check(mid) 成功，说明 mid 可行，尝试更大的解：ans = mid, left = mid + 1。
  • 如果 check(mid) 失败，说明 mid 不可行，缩小范围：right = mid - 1。

2. 复杂度分析

• 排序：$O(N \log N)$。
• 二分：循环 $\log(10^9) \approx 30$ 次。每次 check 遍历数组 $O(N)$。二分部分总复杂度 $O(30N)$。
• 总复杂度：$O(N \log N)$。对于 $N=10^5$ 毫无压力。

3. 标准代码 (C++14)

/**
 * 题目：河西烽火 (Beacons of Hexi)
 * 难度：GESP 6级
 * 算法：二分答案 + 贪心
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 开启 IO 优化
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

int N, M;
vector<int> X;

// 判定函数：判断最小间距为 d 时，能否选出 M 个点
bool check(int d) {
    int count = 1; // 第一个点必选
    int last_pos = X[0];

    for (int i = 1; i < N; ++i) {
        // 如果当前点距离上一个选中的点距离 >= d，则选中当前点
        if (X[i] - last_pos >= d) {
            count++;
            last_pos = X[i];
            
            // 如果已经选够了 M 个，直接返回成功
            if (count >= M) return true;
        }
    }
    return false;
}

int main() {
    fast_io();

    if (!(cin >> N >> M)) return 0;

    X.resize(N);
    for (int i = 0; i < N; ++i) {
        cin >> X[i];
    }

    // 1. 二分答案的前提是有序
    sort(X.begin(), X.end());

    // 2. 二分范围
    // 最小间距可能是 0，最大可能是首尾距离
    int left = 0, right = 1000000000; 
    int ans = 0;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (check(mid)) {
            // 可行，尝试更大的间距
            ans = mid;
            left = mid + 1;
        } else {
            // 不可行，间距太大了
            right = mid - 1;
        }
    }

    cout << ans << endl;

    return 0;
}

第四部分：数据生成器

这是用于生成 1.in ~ 10.in 及其对应标准答案的生成器代码。

/**
 * GESP 6级 [河西烽火] - 数据生成器
 */
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

// ------------------------------------------
// 标准解法函数 (生成 .out)
// ------------------------------------------
bool check_solve(int d, int N, int M, const vector<int>& X) {
    int count = 1;
    int last = X[0];
    for(int i=1; i<N; i++) {
        if(X[i] - last >= d) {
            count++;
            last = X[i];
            if(count >= M) return true;
        }
    }
    return false;
}

int solve(int N, int M, vector<int> X) {
    sort(X.begin(), X.end());
    int l = 0, r = X.back() - X.front();
    int ans = 0;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(check_solve(mid, N, M, X)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

// 辅助函数
int randRange(int min, int max) {
    if (min > max) return min;
    return rand() % (max - min + 1) + min;
}

int main() {
    srand(time(0));
    
    cout << "Start generating data..." << endl;

    for (int i = 1; i <= 10; ++i) {
        string in_name = to_string(i) + ".in";
        string out_name = to_string(i) + ".out";
        ofstream fin(in_name);
        ofstream fout(out_name);

        int N, M;
        vector<int> X;

        // 构造测试点
        if (i == 1) { 
            // 样例1
            N = 5; M = 3; X = {1, 2, 8, 4, 9};
        }
        else if (i == 2) {
            // 样例2
            N = 6; M = 4; X = {1, 4, 9, 15, 20, 25};
        }
        else if (i == 3) {
            // 最小边界 N=2, M=2
            N = 2; M = 2; X = {10, 100};
        }
        else if (i == 4) {
            // 等差数列 (答案固定)
            N = 100; M = 10;
            for(int k=0; k<N; k++) X.push_back(k * 100);
        }
        else if (i == 5) {
            // 密集点，选很少 (答案很大)
            N = 100; M = 2;
            for(int k=0; k<N; k++) X.push_back(k);
        }
        else if (i == 6) {
            // 密集点，选很多 (答案很小)
            N = 100; M = 90;
            for(int k=0; k<N; k++) X.push_back(k*2);
        }
        else if (i == 7) {
            // 坐标值很大
            N = 1000; M = 50;
            for(int k=0; k<N; k++) X.push_back(randRange(1, 1000000000));
        }
        else if (i == 8) {
            // M=N 的情况 (答案就是相邻差的最小值)
            N = 1000; M = 1000;
            int current = 1;
            for(int k=0; k<N; k++) {
                current += randRange(1, 100);
                X.push_back(current);
            }
        }
        else {
            // 大规模随机 (N=10^5)
            N = 100000; 
            M = (i==9) ? 5000 : 2; // Case 9 中等M，Case 10 最小M
            
            // 生成有序随机增量，再打乱
            int current = 1;
            for(int k=0; k<N; k++) {
                current += randRange(1, 1000);
                X.push_back(current);
            }
            random_shuffle(X.begin(), X.end());
        }

        // 写入输入
        fin << N << " " << M << endl;
        for(int k=0; k<N; k++) fin << X[k] << (k==N-1?"":" ");
        fin << endl;

        // 写入输出
        fout << solve(N, M, X) << endl;

        fin.close();
        fout.close();
        cout << "Generated Case " << i << endl;
    }
    
    cout << "Done!" << endl;
    return 0;
}