Regional Contest E Base Station Sites 複現 題解

The 2017 ACM-ICPC Asia Hong Kong Regional Contest E Base Station Sites 複現 題解

• 題目
• • 題意
• 代碼
• • 思路
• 總結

題目

• 同樣與F一樣，是在社團oj上做的題目。

  

  原題連結

題意

• 在L個距離點中選出S個放置基站，并且要求基站之間的最小距離的極限值。

代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int S, L, p[1000000];
    while (1) {
        scanf("%d%d", &L, &S);
        if (L + S == 0) break;
        for (int i = 0; i < L; i++) {
            scanf("%d", &p[i]);
        }
        sort(p, p + L);
        int left = 0, right = 1e6, mid;
        while (left <= right) {
            mid = (left + right) /2;
            int count = 1, pos = 0;
            for (int i = 1; i < L; i++) {
                if (p[i] - p[pos] >= mid) {
                    pos = i;
                    count++;
                }
            }
            if (count >= S)
                left = mid + 1;
            else
                right = mid - 1;
        }
        printf("%d\n", left - 1);
    }
    return 0;
}
           

思路

• 使用二分法，假設答案已經存在，将得出的中值作為區間，在P中尋找滿足區間的點，計數，如果數量大于等于基站數就擴大區間繼續找，反之縮小區間增加滿足條件的點數，最終的

  left-1=right+1

  就是我們要找的滿足條件的最小區間，輸出兩者之一即可。

總結

• 第一次做二分法的題目，這樣二分答案區間的方式和我以前使用二分法查找的思路很不一樣，這道題開拓了我的思路。