fork(1) download 
  1.  
  2. #include<bits/stdc++.h>
  3. #define all(x) x.begin(), x.end()
  4. #define pb(x) push_back(x)
  5. #define N 200005
  6. #define cout2(x, y) cout << x << " " << y << endl
  7.  
  8. using namespace std;
  9.  
  10. int x[N], dis_left[N], dis_right[N];
  11. int ac1[N], ac2[N];
  12.  
  13. int main(){
  14.  
  15. 	int n;
  16. 	while(cin>>n){
  17.  
  18. 		for(int i = 1; i <= n; i++)scanf("%d", &x[i]);
  19. 		sort(x + 1, x + n + 1);
  20.  
  21. 		int total = x[n] - x[1];
  22.  
  23. 		for(int i = 1; i <= n - 1; i++){
  24.  
  25. 			dis_left[i] = x[i + 1] - x[i];
  26. 			ac1[i] = ac1[i - 1] + dis_left[i];
  27. 		}
  28.  
  29. 		for(int i = n; i >= 2; i--){
  30.  
  31. 			dis_right[i] = x[i] - x[i - 1];
  32. 			ac2[i] = ac2[i + 1] + dis_right[i];
  33. 		}
  34.  
  35. 		int maxi = 0;
  36. 		for(int i = 0, j; i <= (n - 1)/2; i++){
  37.  
  38. 			j = (n - 1)/2 - i;
  39. 			maxi = max(maxi, ac1[i] + ac2[n - j + 1]);
  40. 		}
  41.  
  42. 		cout << total - maxi << endl;
  43.  
  44.  
  45. 	}
  46. }
Success #stdin #stdout 0s 7324KB
comments (?)
stdin 
5
1 2 3 4 5
stdout 
2
https://ideone.com/dZcPH2
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!