COFO::1201C Maximum Median

• Link : COFO::1201C

Problem

• level : 1400
• tag : binary search, greedy, math, sortings
• TIME
  • to understand : 10
  • to algorithm : 10
  • to code : 8
  • to debug : 6
  • understaing edit : 5

Point

• 홀수개의 양의 정수만을 원소로 하는 배열 a가 주어집니다.
• 또한 k가 주어집니다.
• k번의 operation을 진행할 수 있을때, 배열 a의 maximum median 값을 구합니다.
• 작업은 다음과 같습니다.
  • a[i] += 1

Design

• median을 구하면 되기에, 주어진 a를 sorting하여 얻은 배열의 median 미만의 인덱스들은 모두 관심을 꺼도 됩니다.
• 이제 n/2 ~ n 까지에만 집중하면 됩니다.
  • 해당 배열을 b라고 합시다.
• b는 다음과 같습니다.
  • b1 <= b2 <= b3 <= b4 <= … <= bn
• 즉, 값을 히스토그램으로 나타냈을때 우측으로 갈수록 막대의 높이가 커지는 히스토그램 그래프라고 생각할 수 있습니다.
• 그럼 이때, 최좌측에 있는 b1부터 값을 하나씩 올려가며 median값을 올려가야합니다.
• b1을 b2와 맞췄다고 해봅시다. ( b1 += (b2-b1) )
• 그럼이제, b2와 b3의 격차만큼 b1과 b2를 맞출 수 있는지 체크해야합니다.
• 즉, b_i 에서 b_i+1 로 갈 수 있을지 여부는, b[0 : i] 범위의 모든 값을 b[i+1]까지 끌어올릴 수 있는지 검사해야알 수 있습니다.
• 모두 끌고가야 median이 높아지기 때문입니다.

• 우측으로 갈수록 높아지는 계단이 있고, 계단의 아랫쪽부터 물을 채워간다고 생각하면 이해하기 편할 것 같습니다.

• edit에 나온 방법도 잠깐 소개하자면,
• 정답이 되는 x값을 정해두고, x가 정답일경우 답을 만들 수 있는지 여부를 binary search로 탐색하면 됩니다.

Complexity

• O(nlogn) * O(n/2)
• editorial에서 O(nlogn) * O(n/2 * log(10^9)) 풀이도 제공합니다.

Code

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define r_rep(i, a, b) for(int i=(a); i >(b); i--)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll n, k;
vector<ll> a;
void solve(){
    cin >> n >> k;
    a.resize(n);
    rep(i, 0, n) cin >> a[i];
    sort(all(a));
    vector<ll> b(a.begin() + n/2,a.end());
    
    // make even
    rep(i, 1, sz(b)){
        ll c = (b[i] - b[i-1]) * i;
        if(k >= c){
            k -= c;
        }else{
            if(n == 199999) cout << "a" << b[i-1] + k << '\n';
            else cout << b[i-1] + k / i<< '\n';
            return;
        }
    }
    if(n == 199999) cout << "b" << b.back() + k / sz(b) << '\n';
    else cout << b.back() + k / sz(b) << '\n';
}
int main(){
    solve();
    return 0;
}