已知最优解

已知最优解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#define MAX_LENGTH 500010
using namespace std;

int total_distance, stone_count, max_remove;
int positions[MAX_LENGTH];
int left_bound, right_bound, mid, answer;

inline int fast_read() {
    int num = 0;
    char c;
    bool is_negative = false;
    
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    
    if (c == '-') {
        is_negative = true;
    } else {
        num = c - '0';
    }
    
    while (isdigit(c = getchar())) {
        num = num * 10 + c - '0';
    }
    
    return is_negative ? -num : num;
}

bool is_possible(int min_distance) {
    int remove_count = 0;
    int current_pos = 0;
    int next_pos = 0;
    
    while (next_pos < stone_count + 1) {
        next_pos++;
        if (positions[next_pos] - positions[current_pos] < min_distance) {
            remove_count++;
        } else {
            current_pos = next_pos;
        }
    }
    
    return remove_count <= max_remove;
}

int main() {
    total_distance = fast_read();
    stone_count = fast_read();
    max_remove = fast_read();
    
    for (int i = 1; i <= stone_count; i++) {
        positions[i] = fast_read();
    }
    positions[stone_count + 1] = total_distance;
    
    left_bound = 1;
    right_bound = total_distance;
    answer = 0;
    
    while (left_bound <= right_bound) {
        mid = (left_bound + right_bound) / 2;
        
        if (is_possible(mid)) {
            answer = mid;
            left_bound = mid + 1;
        } else {
            right_bound = mid - 1;
        }
    }
    
    cout << answer << endl;
    return 0;
}