3127 - 最小差值问题
时间限制 : 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