BOJ)1183 약속

문제: icpc.me/1183

도착하는 시간 A 배열과 기다리는 시간 S배열이 주어질 때 

SUM[ abs(S[i]-A[i]+T) ] 을 최소로 만드는 T의 개수를 세는 것이다.

어짜피 s배열과 a배열 둘다 입력으로 주어지는 수니 수식의 간편화를 위하여 X로 표시할 수 있다

결국 우리는 SUM[ abs(X[i]+T) ]를 구하면 되는 것이다.

X[i]들을 전부 정렬한 후 어떤 수 T를 어떤 수 -X[i]로 잡고 값을 정할 때

T를 -X[i]에서 증가 시킬 경우 (X[i]보다 큰수들-X[i]보다 작은수들)만큼 증가하며 

-X[I]에서 감소 시킬 경우 (X[i]보다 작은수들-X[i]보다 큰수들)만큼 증가하게 된다.

결국 이를 이용하여 생각하면 정렬을 했을 때 중앙값의 음수부호를 취해준 -X[i]가 합을 최소로 만드는 T가 된다.

그런데 N이 홀수일 경우 답은 1개지만 N이 짝수일 경우 X[N/2]과 X[N/2-1]사이의 모든 수들이 합을 최소로 만드는 T가 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
int n, x, y, r, a[10000], s;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &x, &y);
        a[i] = x - y;
    }
    sort(a, a + n);
    if (n % 2)
        printf("1\n");
    else
        printf("%d\n", abs(a[n / 2] - a[n / 2 - 1]) + 1);
    return 0;
}