28、最小化战斗力差距.docx

解题思路

我们假设?max(a)?为?x，min(b)?为?y。求解?|x-y|?的最小值，本质上就是要使得?x和?y?的相对距离最小。对于数组来说，将其排序后，相邻元素之间的相对距离一定是最小的，即答案为数组排序后所有相邻元素差值的最小值。

我们需要考虑这样排序后的构造是否是合法的，实际上可以构造一种满足条件的分组方法：假设对于排序后随意一组相邻的两个元素，左边的元素设为?l，右边的元素为?rr，因为数组有序，所以?l左边的元素均不大于?l，于是我们可以将?l左边的元素和?l视为?a?组；同时?r?右边的元素均不小于?y，我们可以将?r?右边的元素和?rr?视为?bb?组。这样就能够保证?l?一定是?max(a)，r一定是?min(b)，即分组可行。

具体实现时，我们只需要将数组排序，然后在任意两个相邻元素的差值中取最小的即为答案。

时间复杂度为?O(nlogn)?。

AC_Code

C++

#includebits/stdc++.h

usingnamespacestd;

intn;

intmain()

{

ios_base::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cinn;

std::vectorinta(n);

for(inti=0;in;++i)cina[i];

sort(a.begin(),a.end());

intans=1e9;

for(inti=1;in;++i)ans=min(ans,a[i]-a[i-1]);

coutans\n;

return0;

}

Java

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String[]args){

Scannerscan=newScanner(System.in);

intn=scan.nextInt();

int[]a=newint[n];

for(inti=0;in;++i){

a[i]=scan.nextInt();

}

Arrays.sort(a);

intans=Integer.MAX_VALUE;

for(inti=1;in;++i){

ans=Math.min(ans,a[i]-a[i-1]);

}

System.out.println(ans);

}

}

Python

n=int(input())

a=list(map(int,input().split()))

a.sort()

ans=float(inf)

foriinrange(1,n):

ans=min(ans,a[i]-a[i-1])

print(ans)