Codeforces Round 577 (Div. 2) 1201C. Maximum Median Solution

 

Problem Link : https://codeforces.com/contest/1201/problem/C

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. int n , k ;
5. int a[200009] ;
6. bool bs_f(int x){
7. int min_operation = 0 ;
8. for ( int i = (n + 1 )/ 2 ; i <= n ; i++){
9. if (a[i] < x ) {
10. min_operation += ( x - a[i]) ;
11. }
12. if (min_operation > k ) return 0 ;
13. }
14. return 1 ;
15. }
16. int32_t main() {
17. ios_base::sync_with_stdio(0);
18. cin.tie(0);
19. cin >> n >> k ;
20. for ( int i = 1 ; i <= n ; i++){
21. cin >> a[i] ;
22. }
23. sort(a + 1 , a + n + 1 ) ;
24. int l = 0 , r = 2e9 , ans = 0 ;
25. while( l <= r ){
26. int mid = l + (r - l ) / 2 ;
27. if(bs_f(mid)){
28. ans = mid ;
29. l = mid + 1 ;
30. }
31. else {
32. r = mid - 1 ;
33. }
34. }
35. cout << ans <<'\n' ;
36. return 0 ;
37. }