본문 바로가기

알고리즘 관련/BOJ

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가 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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 / - 1]) + 1);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)9470 Strahler 순서  (0) 2017.01.22
BOJ)13711 LCS4  (0) 2017.01.22
BOJ)1183 약속  (0) 2017.01.22
BOJ)2150 Strongly Connected Component  (0) 2017.01.21
BOJ)3176 도로 네트워크  (0) 2017.01.21
BOJ)11983 Radio Contact  (0) 2017.01.21

태그