题目谅解:http://acm.hdu.edu.cn/showproblem.php?pid=4932
不敢然我相信的是,函数参数类型写错了,让我花了好一会儿才找到。
做比赛的时候,就用枚举距离 的。后来才知道,还可能是距离 的一半。
比如这组数据
5
1 2 5 6 8 ans = 1.5。估计有很多被黑到这里了。
思路就是:对于点,要不是线段的左端点,要不就是右端点。所以,对于每个点,都有两个线段选择。往左的优先,往右的之后。
由于最多50条线段,那么直接枚举,距离和距离的一半就好了。
Code:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int N = 55; int n ; bool Judge(double x, double arr[]) { double tol[N], tor[N]; for(int i = 0; i < n; i ++){ tol[i] = arr[i] - x; tor[i] = arr[i] + x; } double tmp[N]; for(int i = 0; i < n; i ++){ tmp[i] = arr[i]; } for(int i = 1; i < n - 1; i ++){ if(tol[i] >= tmp[i - 1]) tmp[i] = tmp[i]; else if(tor[i] <= tmp[i + 1]) { tmp[i] = tor[i]; if(tmp[i] == tmp[i + 1]) i ++; } else return false; } return true; } int main(){ // freopen("1.txt", "r", stdin); int T; scanf("%d", &T); while(T --){ scanf("%d", &n); double arr[N]; for(int i = 0 ; i < n; i ++){ scanf("%lf", &arr[i]); } sort(arr, arr + n); double dis[N]; for(int i = 1; i < n; i ++){ dis[i] = arr[i] - arr[i - 1]; } double ans = 0; for(int i = 1; i < n; i ++){ if(Judge(dis[i], arr)) { ans = max(ans, dis[i]); } if(Judge(dis[i] / 2.0, arr)){ ans = max(ans, dis[i] / 2.0); } } printf("%.3f\n",ans); } return 0; }
对于,函数参数类型写错了,是不可原谅的。写代码的时候,要多思考。