本文主要是介绍HDU4932Miaomiao's Geometry(暴力），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：HDU4932Miaomiao's Geometry(暴力）
题目大意：给出N个点，然后要求你将这些点都覆盖。覆盖的条件，用等长的线段，并且一条线段覆盖这个点要求这个点在这个线段的左端或是右端。
解题思路：一开始就直接暴力，但是题意没有理解清楚，一条线段可以有覆盖两个点的情况。一个点要不作为左端点，要不做为右端点，长度就取暴力中的最小的线段长度，最后再取最大的长度。可是这样会有问题，因为长度大于最短的长度也不能保证这两条线段没有交集。所以只能枚举线段可能的长度。最多100。再验证这个长度是否满足题意。验证的时候就要考虑清楚。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;const int N = 55;int n;
double num[N];
double ans;
int chose[N];//判断是否可以选择作为左端点bool dfs (int k, double len) {if (k == n)return true;if (!k || (chose[k - 1] && num[k] - num[k - 1] >= len))//作为右端点chose[k] = 1;else if (k == n - 1 || num[k + 1] - num[k] >= len) {//作为左端点if (num[k + 1] - num[k] == len || num[k + 1] - num[k] >= 2 * len)chose[k] = 1;else //长度大于len但是小于2 * lenchose[k] = 0;} elsereturn false; //验证失败return dfs (k + 1, len);
}int main () {int T;scanf ("%d", &T);while (T--) {scanf ("%d", &n);for (int i = 0; i < n; i++)scanf ("%lf", &num[i]);sort (num, num + n);ans = 0;for (int i = 1; i < n; i++) {if (ans < num[i] - num[i - 1] && dfs (0, num[i] - num[i - 1]))ans = max (ans, num[i] - num[i - 1]);else if (ans < (num[i] - num[i - 1]) / 2 && dfs (0, (num[i] - num[i - 1]) / 2))ans = max (ans, (num[i] - num[i - 1]) / 2);}printf ("%.3lf\n", ans);}return 0;}
这篇关于HDU4932Miaomiao's Geometry(暴力）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
