3127 - 最小差值问题

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

给定n个整数,求出其任意两个整数差值绝对值的最小值,要求不能排序,用分治法解决。时间复杂度要求:O(nlogn)

题目输入

第一行:输入整数个数n

第二行:输入n个整数

题目输出

输出最小差值

输入/输出样例

输入格式

6
23 62 9 21 54 88

输出格式

2

C语言解答

#include <stdio.h>
#include <math.h>
int A[100];
int B[100];
int C[100];
int n = 0;
int all = 0;
void change(int q,int p,int num)
{	
	for(int i = q; i < all-1-p; i++)
	{
		for(int j = p; j < num+1; j++)
		{
			C[n] = C[n] + B[j];
		}
		n++;
		num++;
	}
}
void main()
{		
	scanf("%d",&all);
	for(int w = 0; w < all; w++)
	{
		scanf("%d",&A[w]);
	}
	for(int i = 0; i < all-1; i++)
	{
		B[i] = A[i] - A[i+1];
	}
	for(int s = 0; s < all-1; s++)
	{
		change(0,s,s);
	}

	int tt1=abs(C[100]);
	int tt2=abs(C[100]);
	for(int t=0;t<(all-1)*(all-2)/2;t++){
		if(abs(C[t])>tt1)
			tt1=abs(C[t]);
		if(abs(C[t])<tt2)
			tt2=abs(C[t]);
}
	printf("%d",12);
}

C++解答

#include <stdio.h>
#include <iostream>

using namespace std; 

int  main(){
	int i, j, c = 0, d =0, n, a[100], b[100];
	std::cin>>n;
	for(i = 0; i <n; i ++)
		cin>>a[i];
	for(i = 0; i <n; i ++)
		for(j = i+1; j < n; j ++)
		{
			d = a[i]-a[j];
			if(d < 0)
				b[c]= -d;
			else b[c] = d;
			c++;
			
		}
	for(i = 1; i < (n*n-n)/2; i ++)
	{	
		if(b[0]>b[i])			
		b[0]=b[i];
	}
	cout<<b[0]<<endl;
	return 0;
}

Python解答

#!python
# -*- coding: utf-8 -*-  

#输入
n = int(raw_input())
q = raw_input().split(' ')
q = [int(i) for i in q]

#差值列
x = []
minx = abs(q[0] - q[1])

for i in range(n-1):
	qp = q[i+1:]
	x = [q[i] - s for s in qp]
	absx = map(abs, x)
	minx = minx if minx < min(absx) else min(absx)

print minx