最大间隙问题
查看 提交 统计 提问
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 128000kB
描述
给定n个实数 x1, x2,..., xn,求这 n个数在实轴上相邻 2 个数之间的最大差值。假设对任何实数的下取整函数耗O(1),设计解最大间隙问题的线性时间算法。
输入
文件的第1 行有1 个正整数n。接下来的1 行中有n个实数 x1,x2,...,xn 。
输出
程序运行结束时,将找到的最大间隙输出到文件中。
样例输入
5
2.3 3.1 7.5 1.5 6.3
样例输出
3.2
我是用浮点数输入,然后排个序,直接输出差值的最大值,不过输出的格式不知道怎么控制。
代码如下
#include“stdio.h”
#include"stdlib.h"
int f(const void a,const void *b)
{
if((float*)a>=*(float*)b)
return 1;
return 0;
}
int main()
{
float a[20],max=0;
int n,i;
scanf("%d",&n);
for(i=0;i
scanf("%f",&a[i]);
qsort(a,n,sizeof(float),f);
for(i=1;i
if(a[i]-a[i-1]>max)
max=a[i]-a[i-1];
}
printf("%0.1f",max);
return 0;
}