首页 > 代码库 > hdu 4932 Miaomiao's Geometry 解题报告
hdu 4932 Miaomiao's Geometry 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4932
题目意思：给出 n 个点你，需要找出最长的线段来覆盖所有的点。这个最长线段需要满足两个条件：（1）每个点是某条线段的左端点或右端点 （2）任意两条线段之间的重叠部分的长度为0。（一个点重叠默认长度为0，即[1，2] ， [2, 3] 视为合法）。还有一点我来补充吧，就是这个最大长度是固定的，看第3组测试数据 1 9 100 10，[-7,1] , [1,9] , [10,18] , [100,108] 长度都为8，不能参差不齐啦~~~~
昨天的BestCoder 4 的 B 题，好多人过pretest，但最终能过final ，寥寥无几啊（当中这行列有我啦），希望过后的失望啊.......天真的做法：每个点求出它两边的间隙，保存较大的那个（因为正常情况下都应该向大的那边扩展啦），然后在所有点的较大的那个中找出最小的那个就是答案了......
const int maxn = 100 + 10;int maxx[maxn], minn[maxn];int a[maxn];int main(){ int T, n; while (scanf("%d", &T) != EOF) { while (T--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a+n); int ll = abs(a[0]-1e9); maxx[0] = max(a[1]-a[0], ll); for (int i = 1; i < n-1; i++) maxx[i] = max(a[i]-a[i-1], a[i+1]-a[i]); int rr = abs(1e9-a[n-1]); maxx[n-1] = max(a[n-1]-a[n-2], rr); double ans = 1e9; for (int i = 0; i < n; i++) ans = min((double)maxx[i], ans); printf("%.3f\n", ans); } } return 0;}
貌似挺多人好像我这样做滴= =。
给组测试数据立马知道出事了！！！！
6
-1 0 10 12 18 20
答案: 3
错误答案：6
如果忽略每两个点之间的间隙/2 而不去逐个测试，也就是只测试 每两个点之间的间隙，那么就 呵呵 了，会得出 2 这个答案，也是错滴！！！ 可以这样想，对于相邻的两个点，它们可以面向对方扩展的嘛，也不一定都要背对着扩展的。
还有一个坑爹的地方，误差！！！一开始对于输出 a real number 就觉得好似是多余的，原来暗示着要测试误差呢。
总的来说，BestCoder 的题目：潜水淹死人！！！
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 #include <cmath> 7 #include <vector> 8 using namespace std; 9 10 #define eps 1e-9 11 #define pb push_back12 const int maxn = 50 + 5;13 vector<double> vd;14 double a[maxn];15 int n;16 17 bool check(double gap)18 {19 double pre = a[0];20 for (int i = 1; i < n; i++)21 {22 if (fabs(a[i]-pre) < eps) // 没这句会wa23 continue;24 if (pre > a[i]) 25 return false;26 else if (pre + gap <= a[i])27 pre = a[i];28 else29 pre = a[i] + gap; // 这一句意味深长啊，如果它更新后比下一个待检测的a[i]大，即： if (pre > a[i]) 就没有继续比较下去的必要30 }31 return true;32 }33 34 int main()35 {36 int T;37 while (scanf("%d", &T) != EOF)38 {39 while (T--)40 {41 scanf("%d", &n);42 for (int i = 0; i < n; i++)43 scanf("%lf", &a[i]);44 sort(a, a+n);45 for (int i = 1; i < n; i++)46 {47 vd.pb(a[i]-a[i-1]);48 vd.pb((a[i]-a[i-1])/2); // 别遗漏49 }50 double ans = 0;51 for (int i = vd.size(); i >= 0; i--)52 {53 if (check(vd[i]))54 ans = max(ans, vd[i]);55 }56 printf("%.3f\n", ans);57 }58 }59 return 0;60 }
姑且归去数学专区吧= =