[BOJ] 1183 - 약속

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

BOJ - 약속

문제 유형: 수학, 정렬

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 128MB

문제

마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.

마법사의 약속 시간은 A1, A2, ..., AN이고, 도착 시간은 B1, B2, ..., BN이다. 약속 시간을 T만큼 미루면, 기다리는 시간의 합은 |Ai + T - Bi|의 합과 같다. 기다리는 시간의 합이 최소가 되는 서로 다른 정수 T의 개수를 구해보자.

 

입력

첫째 줄에 N이 주어진다. 다음 N개의 줄에 Ai, Bi가 주어진다.

 

출력

첫째 줄에 기다리는 시간의 합이 최소인 서로 다른 정수 T의 개수를 출력한다.

 

풀이

우선, b_i - a_i를 각각 구해둔다.

그러고 배열에 담아서 정렬한다.

 

n이 홀수인 경우에, |X - a_1| + |X - a_2| + ... + |X - a_n-1| + |X - a_n|의 합의 최소가 되게 하려면,

X가 a_1 ... a_n의 중앙값이 되는게 유일하다. 그러한 T값은 1개가 유일하다.

짝수인 경우에는, 중앙의 두 값을 포함한 사이의 범위가 그 개수이다.

즉, a_{n/2+1} - a_{n/2}에다가 1을 더하면 된다.

 

코드

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);

  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
  }

  vector<int> d(n);
  for (int i = 0; i < n; ++i) {
    d[i] = b[i] - a[i];
  }

  sort(d.begin(), d.end());

  if (n % 2) {
    cout << "1\n";
  } else {
    int mid1 = d[n / 2 - 1];
    int mid2 = d[n / 2];
    cout << mid2 - mid1 + 1 << "\n";
  }

  return 0;
}