hdu 4932 BestCoder Round #4 1002
2024-10-21 11:50:02
这题真是丧心病狂,引来今天的hack狂潮~
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.
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
3
3
1 2 3
3
1 2 4
4
1 9 100 10
3
1 2 3
3
1 2 4
4
1 9 100 10
Sample Output
1.000
2.000
8.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.
正解还在讨论中,不过有多种,,,被hack掉的。。
后来发现正解是暴力,暴力中的暴力。。。
枚举所有两点之间距离以及距离的一半,然后贪心的放。
对于A[i],能往左放就往左,不行就往右。往右也放不了,就不行了,判断下一个长度。
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<cmath>
#include<queue>
#define N 1005
#define MAXN 1000005
#define M 200
#define mod 1000000007
#define ll long long
using namespace std; int n,m;
int T;
ll a[N],b[N];
ll te;
ll ans; bool cmp(ll x,ll y)
{
return x>y;
} int isok(ll v)
{
ll now=;
for(int i=;i<=n-;i++){
// printf(" %I64d %I64d %I64d now=%I64d v=%I64d\n",a[i+1],a[i],a[i-1],now,v);
// printf(" %d\n",(a[i]-a[i-1]-now) <=v);
if( (a[i]-a[i-]-now) >=v){
now=;
}
else{
if( (a[i+]-a[i]) ==v){
now=;
i++;
}
else if( (a[i+]-a[i]) >v){
now=v;
}
else return ;
}
}
return ;
} int main()
{
int i,j,k;
//freopen("data.txt","r",stdin);
scanf("%d",&T);
//while(scanf("%d",&n)!=EOF)
while(T--)
// for(cnt=1;cnt<=T;cnt++)
{
scanf("%d",&n);
m=;
for(i=;i<=n;i++){
scanf("%I64d",&a[i]);
a[i]*=;
}
sort(a+,a++n);
//for(i=1;i<=n;i++)printf(" %I64d\n",a[i]);
for(i=;i<n;i++){
te=a[i+]-a[i];
b[m]=te;m++;
te/=;
b[m]=te;m++;
}
sort(b,b+m,cmp);
//for(i=0;i<m;i++)printf(" %I64d\n",b[i]);
for(j=;j<m;j++){
if(isok(b[j])==){
printf("%.3f\n",(double)b[j]/);
break;
}
} } return ;
}
最新文章
- 探索C++的秘密之详解extern ";C";,这就是为什么很多.lib被我们正确调用确总是无法解析的。
- 一句命令快速合并 JS、CSS
- 最长公共子串 NYOJ 36
- JavaScript的常见事件和Ajax小结
- SQL用replace替换文本部分内容
- asp.net错误.在应用程序级别之外使用注册为 allowDefinition=&#39;MachineToApplication&#39; 的节是错
- Mysql用户相关操作
- pdf文件之itextpdf操作实例
- js调DLL类库中的方法实现(非com组件形式)
- 【学习】如何安装GraphLab Create 【转载】
- Git使用(二、分支的创建和上传)
- Ios项目添加Pods
- SAP Tax Service可以取代TAXBRA / RVABRA吗?(翻译) 跨国贸易云税务解决方案
- yii框架 隐藏index.php 以及美化URL(pathinfo模式访问)
- 数据库中清空数据,保留表结构的sql语句
- Azure SQL Database (22) Azure SQL Database支持中文值
- [转] offsetParent 到底是哪一个?
- (转)Unity3D工程版本管理方案
- 【转】Linux内核源码分析方法
- RPC框架之Thrift分析(转)