问题描述：河的左岸到右岸之间有一座年久失修、已经废弃的大桥有 N 个桥墩影响船只通行。现在要拆除部分桥墩使得通航能力最大通航能力由最窄的地方决定的这个地方有可能是岸与桥墩之间也可以是桥墩之间。工程预算有限只能拆除 M 个桥墩。如何安排工程才能使得通航能力尽可能的大。第 5 页 共 6 页输入格式：第一行包含三个整数 LNM分别表示左岸到右岸的距离、桥墩数和需要拆除的桥墩数。接下来 N 行每行一个整

#include #include #include using namespace std;

int main() { long long L, N, M; cin >> L >> N >> M; vector bridge(N); for (int i = 0; i < N; i++) { cin >> bridge[i]; } sort(bridge.begin(), bridge.end());

long long left = 0, right = L;
while (left < right) {
    long long mid = (left + right + 1) / 2;
    long long count = 0;
    long long prev = 0;
    for (int i = 0; i < N; i++) {
        if (bridge[i] - prev < mid) {
            count++;
        } else {
            prev = bridge[i];
        }
    }
    if (count <= M) {
        left = mid;
    } else {
        right = mid - 1;
    }
}

cout << left << endl;

return 0;