题目大意：在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;}