BestCoder Round #4 之 Miaomiao's Geometry（2014/8/10）

时间：2014-08-10 21:31:00 阅读：417 评论：0 收藏：0 [点我收藏+]

Miaomiao‘s Geometry

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 10 Accepted Submission(s): 3

Problem Description

There are N point on X-axis . Miaomiao would like to cover them ALL by using segments with same length.

There are 2 limits:

1.A point is convered if there is a segments T , the point is the left end or the right end of T.
2.The length of the intersection of any two segments equals zero.

For example , point 2 is convered by [2 , 4] and not convered by [1 , 3]. [1 , 2] and [2 , 3] are legal segments , [1 , 2] and [3 , 4] are legal segments , but [1 , 3] and [2 , 4] are not (the length of intersection doesn‘t equals zero), [1 , 3] and [3 , 4] are not(not the same length).

Miaomiao wants to maximum the length of segements , please tell her the maximum length of segments.

For your information , the point can‘t coincidently at the same position.

Input

There are several test cases.
There is a number T ( T <= 50 ) on the first line which shows the number of test cases.
For each test cases , there is a number N ( 3 <= N <= 50 ) on the first line.
On the second line , there are N integers Ai (-1e9 <= Ai <= 1e9) shows the position of each point.

Output

For each test cases , output a real number shows the answser. Please output three digit after the decimal point.

Sample Input

Sample Output

1.000 

2.000 

8.000
Hint


For the first sample , a legal answer is [1,2] [2,3] so the length is 1. For the second sample , a legal answer is [-1,1] [2,4] so the answer is 2. For the thired sample , a legal answer is [-7,1] , [1,9] , [10,18] , [100,108] so the answer is 8.
题目大意：

 类似于“区间覆盖”的问题！

 在每组输入n个数，这n个数字是不同的，也就意味着，每两个值之间有差值。

 题目要求用不计数的相等长度线段去覆盖这些点，并且呢，这些点必须在所在小线段的端点上。

 举例说明（上面的第三组数据）：

 a数组： 1 9 100 10       先排一下序，

  --->1  9  10   100    要覆盖这些点，并且这些点都必须在端点上，并且用于

                                覆盖的任何两条线段都不能有重复的部分。

b数组   8   1   90  ---->  相邻两数之间的间距，给b数组也排序。 

      把b数组的值遍历于a数组：思路是：a数组的第一个值和最后一个值可以往外扩展，则不必考虑了。

 现在考虑a数组中间部分的数值，对于每个a[i](i=1--->=n-2)要满足:(a[i]+b[j]<a[i+1] || a[i]-b[j]>a[i-1] ),如果当前的b[j]满足所有的a[i]，则说明b[j]可行，但是我们要找一个最大的b[j].

循环遍历一下b数组找到就行了。

Accepted的代码如下：（可供参考)

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int main()
{
	int t;
	int n;
	int i, j;
	int a[60];
    int b[60], e;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &n);
		for(i=0; i<n; i++)
		{
			scanf("%d", &a[i] );
		}
		sort(a, a+n);
		
		e=0;
		for(i=1; i<n; i++)
		{
			b[e++] = a[i] - a[i-1] ; 
		}
		sort(b, b+n-1 );
		
		int max=-1;
		int flag;
		
		for(i=0; i<n-1; i++)
		{
			flag=1; //初始化每个间距标记
			for(j=1; j<n-1; j++)
			{	
				if(a[j]-b[i]<a[j-1] && a[j]+b[i]>a[j+1] )
				{
					flag=0;
					break;
				}
			}
			if(flag==1)
			{
				if(b[i] >max )
				{
					max = b[i] ;
				}
			}
		}
		printf("%d", max );
		printf(".000\n");
	}
	return 0;
}

 

BestCoder Round #4 之 Miaomiao's Geometry（2014/8/10）,布布扣,bubuko.com

BestCoder Round #4 之 Miaomiao's Geometry（2014/8/10）

原文：http://www.cnblogs.com/yspworld/p/3903330.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)