不能贪心。

贪心hack样例：
4 3
2 4 12 21
正确答案：设置检查点：2,4,10,12,15,18,12。L为3即可，4-10使用技能。
贪心结果为：2,4,8,12,15,17,21。此时L为4，故错误。

可以发现答案满足单调性，意思是如果A是可行解，则所有大于等于A的值都是可行解。

因此可以二分答案，假设一个解 ，然后 O(n) 检测其是否可行。总时间复杂度 O(nlongn)。

这里需要注意一些细节，毕竟是 OI 赛制嘛：

• 第 15 行中每个加一减一想清楚是否需要。
• 第 15 行要与 0 取 max，想清楚题意 ai >= ai-1。
• 第 27 行 l 和 r 的边界，r 取最远端即可，l 最小取 1 即可，取 0 要小心除零错误

参考知乎凉皮大大

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

int n, m;
int a[N];

bool check(int x) {
    int cnt = 0, pre = 0;
    // 模拟，记录需要增加的检查点次数
    for (int i = 0; i < n; i++) {
        cnt += max<int>((a[i] - pre + x - 1) / x - 1, 0);
        pre = a[i];
    }
    return cnt <= m + 1;    // 把技能看作一个检查点
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 二分
    int l = 1, r = a[n - 1];
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    cout << l << endl;
}

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

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

生成随机测试样例

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

void generateTestCases(int numCases) {
    srand(time(0));

    for (int t = 0; t < numCases; ++t) {
        int n = rand() % 9 + 2; // 随机生成 1 到 10 之间的 n
        int m = rand() % 6; // 随机生成 0 到 4 之间的 m

        vector<int> checkpoints(n);
        checkpoints[0] = rand() % 5 + 1; // 第一个检查点的位置

        for (int i = 1; i < n; ++i) {
            checkpoints[i] = checkpoints[i - 1] + rand() % 10 + 1; // 确保每个检查点都比上一个检查点大
        }

        // 打印生成的测试用例
        cout << n << " " << m << endl;
        for (int i = 0; i < n; ++i) {
            cout << checkpoints[i] << " ";
        }
        cout << endl;
    }
}

int main() {
    int numCases;
    cout << "Enter the number of test cases to generate: ";
    cin >> numCases;

    generateTestCases(numCases);

    return 0;
}