fork(1) download
  1. #include<stdio.h>
  2. #include<algorithm>
  3. int n;
  4. int a[200100];
  5. int ans;
  6. int main(){
  7. int i,j;
  8. scanf("%d",&n);
  9. for(i=0;i<n;i++){
  10. scanf("%d",&a[i]);
  11. }
  12. std::sort(a,a+n);
  13. ans=1999999999;
  14. if(n%2==0){
  15. for(i=0;i+n/2<n;i++){
  16. if(a[i+n/2]-a[i]<ans){
  17. ans=a[i+n/2]-a[i];
  18. }
  19. }
  20. }
  21. else{
  22. j=0;
  23. for(i=0;i+(n+1)/2<n;i++){
  24. while(j<n-1&&a[i+(n+1)/2]+a[i]>a[j]+a[j+1]){
  25. j++;
  26. }
  27. if(ans>a[i+(n+1)/2]-a[j])ans=a[i+(n+1)/2]-a[j];
  28. if(ans>a[j]-a[i])ans=a[j]-a[i];
  29. }
  30. }
  31. printf("%d",ans);
  32. return 0;
  33. }
  34.  
Success #stdin #stdout 0s 4240KB
stdin
5
1 2 3 4 6
stdout
1