盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码
  5. 更新日志

HDU 4932 Miaomiao's Geometry(想法)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4932

题意

给定一些点,要用一些等长的线段去覆盖这些点。问这些线段最长可以为多少?这些线段不能够相交,并且点只能够在线段的两个端点。

思路

我一上来就是二分。wa成狗。。
其实二分是不对的,如0,1,4,5 答案为3,但是2不行
仔细想想,其实会发现答案一定其中两个相邻点之间距离或者距离的一半。因为如果距离小于一半,那么可以扩大,扩到一半,这样两个线段相交。如果大于一半,小于该距离,同样可以扩大到该距离位置。对每个可行值进行判断即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#define eps 1e-7
int t, n;
double a[100];
using namespace std;
bool check(double x) {
double now = a[0];
for (int i = 1; i < n - 1; i++) {
if (now == a[i]) continue;
if (a[i] - now >= x) now = a[i];
else if (a[i] + x <= a[i + 1]) now = a[i] + x;
else return false;
}
return true;
}
int main () {
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%lf", a + i);
sort(a, a + n);
/* 二分有问题
double l = 1.0, r = a[n - 1] * 1.0 - a[0], mid;
while(fabs(l - r) > eps) {
mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
*/
double ans = 0;
for (int i = 1; i < n; i++) {
double tmp = a[i] - a[i - 1];
if (check(tmp)) ans = max(ans, tmp);
else if (check(tmp / 2)) ans = max(ans, tmp / 2);
}
printf("%.3f\n", ans);
}
return 0;
}

更新日志

  • 14208548 2015-07-27 22:17:31 Accepted 4932 15MS 1608K 1022B G++ SIO__Five