티스토리 뷰

알고리즘 관련/BOJ

BOJ)1183 약속

JASON 자손9319 2017. 1. 22. 15:20

문제: 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
TAG
댓글
댓글쓰기 폼