竞赛讨论区 > 当N<=M时直接输出L,这个判断居然占了大概86%的测试点
头像
GDUT_21_罗拓展
发布于 09-09 23:14 广东
+ 关注

当N<=M时直接输出L,这个判断居然占了大概86%的测试点

...
#当N<=M时直接输出L,这个判断居然占了大概86%的测试点,离了个特朗普
```
#include c++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL n, m, k, INF;
LL g[N];

bool C(int d) {
    int last = 0;
    for (int i = 1; i <= m - k; i++) {
        int crt = last + 1;
        while (crt < m + 1 && g[crt] - g[last] < d) crt++;
        if (crt == m + 1) return false;
        last = crt;
    }
    if (g[m + 1] - g[last] < d) return false;
    return true;
}

int main() {
    cin >> n >> m >> k;
    if (m <= k) {
            cout << n;
            return 0;
        }
    g[0] = 0, g[m + 1] = n;
    for (int i = 1; i <= m; i++) {
        cin >> g[i];
        INF = max(INF, g[i]);
    }
    int l = 0, r = INF;
    while (l + 1 < r) {
        int mid = l + r >> 1;
        if (C(mid)) l = mid;
        else r = mid;
    }
    cout << l;
    return 0;
}
```

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

近期热帖

等你来战

查看全部

热门推荐