C++最大间隙

C++最大间隙

Scroll Down

QHQ-【问题描述】给定n个实数x1,x2,...,xn, 求着n个数在实轴上相邻两个数之间的最大差值。假设对任何实数的下取整函数好事O(1), 设计解最大间隙问题的线性时间算法。


【问题描述】给定n个实数x1,x2,...,xn, 求着n个数在实轴上相邻两个数之间的最大差值。假设对任何实数的下取整函数好事O(1), 设计解最大间隙问题的线性时间算法。

算法设计:对于给定的n个实数x1,x2,...,xn,计算它们的最大间隙。(只有一位小数)

【输入形式】第一行有1个正整数n(n不超过10),接下来的1行有n个实数x1,x2,...,xn,中间用空格隔开。

【输出形式】输出找到的最大间隙
【样例输入】

5

2.3 3.1 7.5 1.5 6.3
【样例输出】3.2(保留一位小数)
#include<iostream>
#include<iomanip>
using namespace std;
const int MAX = 200001;
double num[MAX];
bool run()
{
	int n;
	if (scanf_s("%d", &n) == EOF) return false;
	int i;
	double max = 0.0, min = INT_MAX;
	for (i = 0; i < n; i++)
	{
		scanf_s("%lf", &num[i]);
		if (num[i] > max) max = num[i];
		if (num[i] < min) min = num[i];
	}

	int* cnt = new int[n];
	double* low = new double[n];
	double* high = new double[n];
	for (i = 0; i < n; i++)
	{
		cnt[i] = 0;
		low[i] = max;
		high[i] = min;
	}

	double ave = (max - min) / (n - 1);

	for (i = 0; i < n; i++)
	{
		int tmp = (int)((num[i] - min) / ave);
		cnt[tmp]++;
		if (num[i] > high[tmp]) high[tmp] = num[i];
		if (num[i] < low[tmp]) low[tmp] = num[i];
	}

	double t = high[0], res = 0.0;
	for (i = 1; i < n; i++)
	{
		if (cnt[i] > 0)
		{
			double tmp = low[i] - t;
			if (tmp > res)   res = tmp;
			t = high[i];
		}
	}
	cout << fixed << setprecision(1) << res << endl;

	return true;
}
int main()
{
	while (run());
	return 0;
}
  1. 因为我用的是vs2019,所以在scanf输出的时候会出现 ***C6031:返回值被忽略的问题:“scanf”***,所以需要改写scanf为scanf_s。
  1. 题目要求结果有一位小数,在C++中,是没有格式符的,所以想起用***setprecision()*** 函数,但是使用这个函数,需要在头文件引入 ***#include***,使用方式在此再简单回顾一下:
cout << setprecision(2) << res <<endl;

这是保留小数点后两位(但是如果结果是整数则是整数,不自动 补零)

cout << fixed << setprecision(1) << res << endl;

在前面加上 fixed 就可以自动补零。

3.再次附一个小吕哥的源码:

#include<bits/stdc++.h>
#define MAXINT 100000
using namespace std;

int main()
{
 int n;
 cin >> n;
 cout << endl;
 double a[MAXINT] = {0.0 };
 for(int i = 0;i < n;i++){
     cin >> a[i];
 }
 sort(a,a+n);
 double maxsub = 0.0;
 double temp = 0.0;
 for(int i = 0;i < (n - 1);i++){
     temp = fabs(a[i] - a[i + 1]);
     if(maxsub < temp){
         maxsub = temp;
     }
 }
 cout << fixed << setprecision(1) << maxsub;
}