笔试时间：2023年9月15日 秋招

第一题

题目：照明灯安装

你负责在一条笔直的道路上安装一些照明灯。但是道路上并不是任意位置都适合安装照明灯，具体地，假设将道路看作一条起点坐标为0，终点坐标为M的线段，那么只有在x1,x2,...,xn这n个坐标可以安装照明灯，且每个坐标上最多只能安装一个照明灯。现在你要在道路上安装k个照明灯，为了使照明灯能够尽量覆盖道路，你需要使距离最近的两个照明灯尽量远。请问这个最近距离最大可以是多少?

输入描述

第一行是两个整数n、k，分别表示可以安装照明灯的位置数和需要安装的照明灯数量。

接下来一行n个整数x1,x2,...,xn表示可以安装照明灯的坐标。保证x1<x2<...<xn。

1<=k<=n<=100000,1<xi<1000000

输出描述

一行，一个整数，表示最近距离的最大值.

样例输入

5 3

1 3 4 7 9

样例输出

3

提示

分别放在1、4、7的位置(放在1、4、9也可以)

能够证明3是最小的最大距离。

参考题解

二分

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool check(const vector<int>& a, int k, int dis) {
    int cnt = 1;
    int last = a[0];
    for (int i = 1; i < a.size() && cnt < k; i++) {
        if (a[i] >= last + dis) {
            cnt++;
            last = a[i];
        }
    }
    return cnt >= k;
}

int main() {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int l = 0, r = 1e9, ans = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(a, k, mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] a = new int[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int l = 0;
        int r = 1000000000;
        int ans = -1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (check