fork download
copy 
  1. //tenary search 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int maxN = 2e5;
  5. int n;
  6. int a[maxN];
  7. long long f(int x){
  8. 	long long sum = 0;
  9. 	for(int i = 0; i < n; i++){
  10. 		sum += abs(a[i] - x);
  11. 	}
  12. 	return sum; 
  13. }
  14. signed main(){
  15. 	cin >> n;
  16. 	for(int i = 0; i < n; i++){
  17. 		cin >> a[i];
  18. 	}
  19. 	int l = 1, r = *max_element(a, a + n);
  20. 	int ans = 0;
  21. 	while(l <= r){
  22. 		int mid = (l + r) / 2;
  23. 		if(f(mid) <= f(mid + 1)){
  24. 			r = mid - 1;
  25. 			ans = f(mid);
  26. 		}else{
  27. 			l = mid + 1;
  28. 		}
  29. 	}
  30. 	cout << ans << endl; 
  31.  
  32. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
5
2 3 1 5 2
stdout
copy 
5
https://ideone.com/rXot40
language:
C++14 (gcc 8.3)
created:
3 days 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!