UVa 11516. WiFi

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](https://uva.onlinejudge.org/external/115/11516.pdf) 翻譯來源:[Luckycat](http://luckycat.kshs.kh.edu.tw/homework/q11516.htm)

Solution

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

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

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

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

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

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

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

假設最大距離為$t$成立,則可以用反證法證明$t+1$時仍成立,接著用數學歸納法可得$t\text{~}(最大門牌號碼-最小門牌號碼)/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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*************************************************************************
> File Name: 11516 - WiFi.cpp
> Author: Samuel
> Mail: en[email protected]
> 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;
}