悬关!!蒟蒻二分求助
查看原帖
悬关!!蒟蒻二分求助
1179393
Noldo楼主2024/3/26 20:56
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5;
int l, n, m;
int sign[N];
bool check(int x) {//最小空旷指数
    int now = 0; int i = 1;
    int cnt = 0;
    while (1) {
        if (i >= n)break;
        if (sign[i] - sign[now] < x) {//若是两个相邻路标相减小于x,说明有比x更小的最小空旷指数,给出的x是错误的
            return false;
        }
        else {
            if ((sign[i] - sign[now] + 1) / 2 > x) {//如果两相邻路标相减再除2得出的距离大于最小路标,则说明这两个路标之间是可以放置新路标的,但在此处,楼主对>x和>=x的条件设置比较模糊
                cnt++; now = i; i++;//设置好新路标后,更新下次循环时要判断的路标                   
            }
            else {
                return false;
            }
        }
    }
    if (cnt >= m)return true;
    else return false;
}
int main() {
    cin >> l >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> sign[i];
    }
    int r = l + 1; int l = -1;
    while (l + 1 != r) {
        int mid = (l + r) / 2;
        if (check(mid))l = mid;
        else r = mid;
    }
    //while结束后的二分顺序应该是这样?-->   ××...×l|r√...√
    cout << r<< endl;
    return 0;
}
2024/3/26 20:56
加载中...