c575. 基地台

思路

1. 一開始先排序數組，方便後續判斷指定的直徑，能否在擺放 $k$ 個基地台的限制下，覆蓋到所有服務點。
2. 用二分查找找到滿足條件的最小直徑。

• 在判斷直徑是否能覆蓋所有房子的時候，先得到基地台覆蓋的結尾，再去判斷服務點有沒有在範圍內。

程式碼

二分查找

#include <iostream> 
#include <algorithm>
using namespace std;
const int MX = 50001;
int nums[MX];
int n, k;

bool check(int diameter) {
    // 最多只能放 k 個基地台，問在直徑為 diameter 的情況下能不能擺放
    int cnt = 1; // 基地台數量
    int end = nums[0] + diameter; // 第一個基地台能覆蓋的結尾
    for(int i = 1; i < n; i++) {
        if(nums[i] > end) {
            if(++cnt > k) return false;
            end = nums[i] + diameter;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums, nums + n);
    int left = 0, right = (nums[n - 1] - nums[0]) / k + 1; // 基地台的半徑上限，開區間。
    while(left + 1 < right) {
        int mid = left + (right - left) / 2;
        (check(mid) ? right : left) = mid;
    }
    cout << right;
}

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$