BOJ 23090 난민

https://www.acmicpc.net/problem/23090

23090번: 난민

 

블로그에 올렸던 쌀 창고 + 중앙값 구하기인 문제입니다.

 

https://havana723.tistory.com/16

BOJ 5821 쌀 창고

https://www.acmicpc.net/problem/2696

2696번: 중앙값 구하기

 

x값의 경우 정수시설의 x축 좌표가 항상 0이므로 고려할 필요 없이 절댓값을 답에 더해주면 됩니다. y값의 경우 쌀 창고와 농구 골대에서 썼던 아이디어를 이용하면 정수시설이 y값들의 중앙값에 있을 때 거리가 최소가 된다는 것을 알 수 있습니다.

 

매 쿼리마다 중앙값을 구하기 위해 중앙값 구하기의 아이디어를 이용하여 우선순위 큐 두 개를 사용해 구합니다. 중앙값을 기준으로 중앙값보다 큰 값을 기록하는 최소 우선순위 큐를 하나, 중앙값을 기준으로 중앙값과 같거나 작은 값을 기록하는 최대 우선순위 큐를 하나 만든 뒤 양 큐의 크기가 같게 유지하면 중앙값을 바로 구할 수 있습니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long

using namespace std;

int T, n;

int32_t main(void) {
  FastIO;
  T = 1;
  //cin >> T;

  while (T--) {
    cin >> n;

    priority_queue<int, vector<int>, greater<int>> big;
    priority_queue<int> small;

    int xsum = 0;
    int ssum = 0;
    int bsum = 0;

    while (n--) {
      int x, y;
      cin >> x >> y;

      int prevm = 0;
      if (!small.empty()) prevm = small.top();

      xsum += abs(x);

      if (big.size() >= small.size()) {
        small.push(y);
        ssum += y;
      }
      else {
        big.push(y);
        bsum += y;
      }

      while (!big.empty() && !small.empty() && big.top() < small.top()) {
        int a = big.top();
        int b = small.top();

        big.pop();
        small.pop();

        big.push(b);
        small.push(a);

        bsum -= a;
        ssum -= b;
        bsum += b;
        ssum += a;
      }


      int nowm = small.top();
      int nowb = big.size();
      int nows = small.size();

      int ans = xsum;
      ans += (nows * nowm) - ssum;
      ans += bsum - (nowb * nowm);

      cout << nowm << ends << ans << endl;
    }
  }

  return 0;
}