UVa 11516. WiFi

2019-02-26

Description

大街上的居民開會決定要在他們居住的街上安裝無線網路，讓無線網路環境涵蓋所有住戶，請你幫忙選擇無線網路基地台(AP)的地點，他們希望訊號愈強愈好，但他們購買AP的預算有限，在有限的AP數量之下，使得在「所有房子與其最近的AP之間的距離」中最大值，愈小愈好。

大街是直線的，每間房子的門牌號碼剛好等於與端點的距離，例如123號的住戶，距離大街的起點為123公尺

Input Format

輸入的第一列有一個整數表示測試資料的組數。
接下來每組測試資料的第一列有兩個正整數$n,m$，$n$ 表示居民所購買的AP總數，$m$ 表示住戶總數。
接下來的 $m$ 列，每列表示一個住戶的門牌號碼。大街上不超過$10^5$個住戶，且門牌號碼不超過一百萬。

Output Format

請每組資料輸出一個數值，表示「所有住戶與其最近的AP間的距離」之最大值，請四捨五入到小數點下第一位。

Sample Input

1 23 1
3 10

Sample Output

1.0

UVa - 11516
翻譯來源：Luckycat

Solution

這題的解法可以分成兩部分：

假設已決定所有住戶到最近基地台的最大距離，要如何檢查是否存在至少一種擺法？
要如何決定所有住戶到最近基地台的最大遠距?

假設已決定所有住戶到最近基地台的最大距離，要如何檢查是否存在至少一種擺法?

首先先解決第一個問題。假設我從左邊一路擺AP擺到右邊，且已知最大距離為$t$，那利用貪心可推論出上第一個AP一定要擺在$第一個住戶位置+t$的地方，接著到下一個沒有被涵蓋在範圍內的住戶($位置>第一個住戶位置+2t$，再用剛剛的想法一路擺下去。
由貪心法可知道上述的擺法一定是最佳解，所以也可以知道總共需要擺多少個AP，若AP數量超過題目給的大小，則可以知道「最大距離為$t$」不可行。

時間複雜度：$O(n)$

要如何決定所有住戶到最近基地台的最大遠距?

題目會給住戶的門牌號碼，所以在最差的情況下答案就是$(最大門牌號碼-最小門牌號碼)/2$，而最佳的擺法則是$0$。
所以可以從$0\sim$ (最大門牌號碼-最小門牌號碼)/2一路搜索下去。可是這樣的會時間複雜度會變成$O(n*檢查的複雜度) = O(n^2)$，很明顯地會TLE，所以需要一個比較好的方法。

假設最大距離為$t$成立，則可以用反證法證明$t+1$時仍成立，接著用數學歸納法可得$t\sim (最大門牌號碼-最小門牌號碼)/2$接成立。若$t$不成立，則也可以用上述的想法推得$t-1$時也是不成立。
所以t從小到大，一定是類似這樣排列：

X: 不成立
O: 成立
X X X ... X O O O ... O

如果有這樣類似的特點，我們可以利用「單調性」來做二分搜。下界跟上界分別為$0$和$(最大門牌號碼-最小門牌號碼)/2$，每次去找中間點並用$O(n)$的方法來檢查是否成立。若不成立，則令下界=mid+1，否則令上界=mid。

時間複雜度：$O(nlogn)$

Code

/*************************************************************************
  > File Name: 11516 - WiFi.cpp
  > Author: Samuel
  > Mail: enminghuang21119@gmail.com
  > Created Time: Sat Dec 30 19:33:04 2017
*************************************************************************/

#include <cstdio>
#include <algorithm>
using namespace std;
int house[100005];
int ap, n, mx;
bool check(int mid) {
    int count = 0;
    int i, j;
    int mid2 = mid * 2;
    i = j = 0;
    while (1) {
        while (house[j] <= house[i] + mid2 && j < n)
            j++;
        count++;
        i = j;
        if (count > ap)
            return false;
        if (j >= n)
            return true;
    }
}
int main() {
    int count;
    scanf("%d", &count);
    while (count--) {
        scanf("%d%d", &ap, &n);
        for (int i = 0; i < n; i++)
            scanf("%d", house + i), house[i] *= 2;
        if (ap >= n) {
            printf("0.0\n");
            continue;
        }
        sort(house, house + n);
        mx = house[n - 1];
        int down, up;
        int mid;
        down = 0;
        up = house[n - 1];
        while (up - down > 1) {
            mid = (down + up)/2;
            if (check(mid))
                up = mid;
            else
                down = mid;
        }
        printf("%.1f\n", up / 2.0);
    }
    return 0;
}