【題解】ZeroJudge c575: APCS 2017-0304-4基地台

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c575
【解題想法】二分搜 (Binary Search)【筆記

  • 題目要求以 K 個基地台覆蓋 N 個服務點。
  • 題目提供 N 個服務點的座標,但沒有按照座標大小排序。讀入測資後,先排序。
  • 如果第一個服務點和最後一個服務點之間的距離 dis <= 2,不用計算,答案直接為 1。
  • 否則的話,進行二分搜來決定最佳基地台間距,搜尋範圍:
    • 最小 mn = 1
    • 最大 mx = int(dis / k) + 1
    • 每次計算中間值 mid 後,重新測試是否用 K 個基地台,就能覆蓋 N 個服務點。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int N, K;
int P[maxn];

bool canCover(int d){
    int coverage = P[0] + d;
    int cnt = 1;
    for (int i=1; i<N; i++){
        while (P[i] > coverage){
            coverage = P[i] + d;
            cnt++;
        }
    }
    return (cnt <= K);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> K;
    for (int i=0; i<N; i++){
        cin >> P[i];
    }
    sort(P, P+N);
    
    int l = 0;
    int r = (P[N-1] - P[0]) / K + 1;
    int mn = 2e9;
    while (l < r){
        int mid = (l + r) / 2;
        if (canCover(mid)){
            mn = mid;
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << mn << '\n';
    
    return 0;
}

Python code

while True:
    try:
        n, k = map(int, input().split())
        lst = list(map(int, input().split()))
        lst.sort()
        
        dis = lst[-1] - lst[0]
        if dis <= 2:
            print(1)
            continue

        mn = 1
        mx = int(dis/k) + 1

        while True:
            mid = (mn + mx) // 2
            count = 0
            start = 0
            for j in range(k):
                dis2 = lst[start] + mid
                count += 1
                for l in range(start, n):
                    if lst[l] > dis2:
                        start = l
                        break
                else:
                    mx = mid
                    break
            else:
                mn = mid + 1

            if mn == mx:
                print(mn)
                break
    except:
        break
分享本文 Share with friends