Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem B: WiFi

One day, the residents of Main Street got together and decided that they would install wireless internet on their street, with coverage for every house. Now they need your help to decide where they should place the wireless access points. They would like to have as strong a signal as possible in every house, but they have only a limited budget for purchasing access points. They would like to place the available access points so that the maximum distance between any house and the access point closest to it is as small as possible.

Main Street is a perfectly straight road. The street number of each house is the number of metres from the end of the street to the house. For example, the house at address 123 Main Street is exactly 123 metres from the end of the street.

Input Specification

The first line of input contains an integer specifying the number of test cases to follow. The first line of each test case contains two positive integers n, the number of access points that the residents can buy, and m, the number of houses on Main Street. The following m lines contain the house numbers of the houses on Main Street, one house number on each line. There will be no more than 100 000 houses on Main Street, and the house numbers will be no larger than one million.

Sample Input

1
2 3
1
3
10

Output Specification

For each test case, output a line containing one number, the maximum distance between any house and the access point nearest to it. Round the number to the nearest tenth of a metre, and output it with exactly one digit after the decimal point.

Output for Sample Input

1.0

---

因為是整數座標，答案一定是落在 x.0 或者是 x.5。那我們全部換成整數運算即可。
二分搜答案，用 Greedy 去判定。
 
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
int A[100005];
int n, m, i, l, r, mm;
int greedy(int mm) {
    static int cnt;
    static int r;
    cnt = 1;
    r = A[0] + mm;
    for(i = 0; i < m; i++) {
        if(abs(r-A[i]) <= mm) {}
        else {
            cnt++;
            if(cnt > n) return 0;
            r = A[i] + mm;
        }
    }
    return 1;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    scanf("%*d");
    while(scanf("%d %d", &n, &m) == 2) {
        for(i = 0; i < m; i++)
            ReadInt(&A[i]), A[i] *= 2;
        sort(A, A+m);
        l = 0, r = (A[m-1]-A[0])/2;
        while(l <= r) {
            mm = (l+r)/2;
            if(greedy(mm)) {
                r = mm-1;
            } else
                l = mm+1;
        }
        printf("%.1lf\n", (r+1)/2.0);
    }
    return 0;
}