hdu 4932 Miaomiao's Geometry(暴力)

hdu 4932 Miaomiao's Geometry(暴力)

題目鏈接：hdu 4932 Miaomiao's Geometry

題目大意：在x坐標上又若干個點，現在要用若干條相等長度的線段覆蓋這些點，若一個點被一條線段覆蓋，則必須在這條線的左端點或者是右端點，並且各個線段放的位置不能又重疊，求最大長度。

解題思路：這題有坑點，比賽的時候o(n)的算法去尋找兩點之間最短距離。但起始這樣是不行的，比如-1 0 10 12 18 20，這樣維護過去的話，最短應該是12~18，長度為6，這段線段可以覆蓋12和18的點，然後-1和20又在兩端。於是只有0和10兩點，0和10之間的長度為10，大於6，所以一段不夠，兩端又有重疊。
賽後的做法，枚舉兩點之間的長度，以及長度的一半，判斷是否可行，維護最大值。

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 100;

int n;
double arr[maxn];

bool judge (double w) {
    double tmp = arr[0];

    for (int i = 1; i < n; i++) {
        if (fabs(arr[i] - tmp) < 1e-9 || arr[i] - tmp > w || fabs(arr[i] - tmp - w) < 1e-9)
            tmp = arr[i];
        else if (arr[i] < tmp)
            return false;
        else
            tmp = arr[i] + w;
    }
    return true;
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%lf", &arr[i]);
        sort(arr, arr + n);

        double ans = 0;
        for (int i = 1; i < n; i++) {
            if (judge (arr[i] - arr[i-1]))
                ans = max(ans, arr[i] - arr[i-1]);
            else if (judge((arr[i] - arr[i-1]) / 2))
                ans = max(ans, (arr[i] - arr[i-1]) / 2);
        }

        printf("%.3lf\n", (double)ans);
    }
    return 0;
}