NeQrhk 2015-11-30 09:37 采纳率: 30.6%
浏览 1344

问一道acm问题,帮忙看下谢谢了

最大间隙问题
查看 提交 统计 提问
总时间限制: 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;
}

  • 写回答

1条回答 默认 最新

  • lx624909677 2015-11-30 10:56
    关注
    #include<iostream.h>
      #include<stdio.h>
      double a[1000000];
      template<class Type>
      void swap(Type &x,Type &y)
      {
      Type temp=x;
      x=y;
      y=temp;
      }
      template<class Type>
      int Partition(Type *a,int low,int high)
      {
      Type pivotkey;
      int mid=(low+high)/2;
      if((a[low]<a[mid]&&a[mid]<a[high])||(a[low]>a[mid]&&a[mid]>a[high]))
      swap(a[low],a[mid]);
      if((a[low]<a[high]&&a[mid]>a[high])||(a[low]>a[high]&&a[mid]<a[high]))
      swap(a[low],a[high]);
      pivotkey=a[low];
      int i=low;
      int j=high+1;
      while(true)
      {
      while(a[++i]<pivotkey);
      while(a[--j]>pivotkey);
      if(i>=j) break;
      swap(a[i],a[j]);
      }
      a[low]=a[j];
      a[j]=pivotkey;
      return j;
      }
      template<class Type>
      void Quicksort(Type *a,int low,int high)
      {
      if(low<high)
      {
      int q=Partition(a,low,high);
      Quicksort(a,low,q-1);
      Quicksort(a,q+1,high);
      }
      }
      template<class Type>
      Type maxtap(Type *a,int n)
      {
      Type maxtap=0;
      for(int i=0;i<n-1;i++)
      maxtap=(a[i+1]-a[i])>maxtap?(a[i+1]-a[i]):maxtap;
      return maxtap;
      }
       main()
      {
       int i,n;
       scanf("%d",&n);
       for(i=0;i<n;i++)
       scanf("%lf",&a[i]);
       Quicksort(a,0,n-1);
       printf("%lf",maxtap(a,n));
       return 0; 
    
    评论

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能