题面描述

云某公司在基地搬迁到新地点后，规划了一条经过 $N$ 个小区的班车路线。公司计划在这些小区中挑选出 $M$ 个小区作为上车点。小区的位置可以用一维坐标上的整数点表示。每个小区到最近上车点的距离为这两个坐标点差值的绝对值。若小区本身被选为上车点，则其到上车点的距离为 $0$。

任务：在给定 $N$ 个小区的位置的情况下，选择 $M$ 个上车点，使得所有小区到最近上车点的距离的最大值尽可能小。计算这个最大值的最小值。

思路

二分答案。二分这个最小可能值$mid$，如何$check$呢?我们贪心的考虑，我们放车站的时候尽可能大的覆盖到右边的区域，最多能覆盖盖$positions[i] + mid$这个位置，我们将下一个位置跳到upper_bound(positions.begin(), positions.end(),positions[i] + mid) - positions.begin();即可，最后检查车站数量是否不超过m即可

cpp

#include <bits/stdc++.h>
using namespace std;

// 函数用于判断在最大距离为mid时，是否可以用不超过M个上车点覆盖所有小区
bool canPlaceStations(const vector<int>& positions, int N, int M, int mid) {
    int count = 0; // 已放置的上车点数量
    int i = 0; // 当前检查的小区索引

    while (i < N) {
        count++; // 放置一个新的上车点
        // 找到最右边的一个小区，使得它不超过 positions[i] + mid
        int station_pos = positions[i] + mid;
        int j = upper_bound(positions.begin(), positions.end(), station_pos) - positions.begin();
        j--; // 上车点放置在 positions[j]

        // 现在，所有小区 <= positions[j] + mid 都被覆盖
        int cover_limit = positions[j] + mid;
        i = upper_bound(positions.begin(), positions.end(), cover_limit) - positions.begin();
    }

    return count <= M;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, M;
    cin >> N >> M;
    vector<int> positions(N);
    for(auto &x : positions) cin >> x;
    
    int left = 0;
    int right = positions[N-1] - positions[0];
    int answer = right;
    
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(canPlaceStations(positions, N, M, mid)){
            answer = mid;
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    
    cout << answer;
}

python

def can_place_stations(positions, N, M, mid):
    count = 0  # 已放置的上车点数量
    i = 0  # 当前检查的小区索引

    while i < N:
        count += 1  # 放置一个新的上车点
        station_pos = positions[i] + mid
        # 找到最右边的一个小区，使得它不超过 positions[i] + mid
        j = i
        while j < N and positions[j] <= station_pos:
            j += 1
        j -= 1  # 上车点放置在 positions[j]

        cover_limit = positions[j] + mid
        # 找到第一个超过 cover_limit 的小区
        while i < N and positions[i] <= cover_limit:
            i += 1

    return count <= M


def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N, M = map(int, data[:2])
    positions = list(map(int, data[2:2 + N]))

    left = 0
    right = positions[-1] - positions[0]
    answer = right

    while left <= right:
        mid = (left + right) // 2
        if can_place_stations(positions, N, M, mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    print(answer)


if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 函数用于判断在最大距离为mid时，是否可以用不超过M个上车点覆盖所有小区
    public static boolean canPlaceStations(int[] positions, int N, int M, int mid){
        int count = 0; // 已放置的上车点数量
        int i = 0; // 当前检查的小区索引

        while (i < N){
            count++; // 放置一个新的上车点
            int station_pos = positions[i] + mid;
            // 找到最右边的一个小区，使得它不超过 positions[i] + mid
            int j = i;
            while (j < N && positions[j] <= station_pos){
                j++;
            }
            j--; // 上车点放置在 positions[j]
            
            // 现在，所有小区 <= positions[j] + mid 都被覆盖
            int cover_limit = positions[j] + mid;
            while (i < N && positions[i] <= cover_limit){
                i++;
            }
        }
        return count <= M;
    }

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        int N = Integer.parseInt(first[0]);
        int M = Integer.parseInt(first[1]);
        String[] posStr = br.readLine().split(" ");
        int[] positions = new int[N];
        for(int i=0;i<N;i++) positions[i] = Integer.parseInt(posStr[i]);
        
        int left =0;
        int right = positions[N-1] - positions[0];
        int answer = right;
        
        while(left <= right){
            int mid = left + (right - left)/2;
            if(canPlaceStations(positions, N, M, mid)){
                answer = mid;
                right = mid -1;
            }
            else{
                left = mid +1;
            }
        }
        System.out.println(answer);
    }
}