레이팅 미적용설명
선물 포장 공방에 상자 \(N\)개와 뚜껑 \(N\)개가 있다. 상자와 뚜껑에는 각각 크기가 적혀 있다.
모든 상자에 뚜껑을 정확히 하나씩 짝지어 덮어야 한다. 상자 크기 \(a\)에 뚜껑 크기 \(b\)를 짝지으면 \(|a - b|\)만큼 모양이 어긋난다.
짝짓기를 잘 했을 때, 어긋남의 합의 최솟값을 구하여라.
제약
- \(1 \le N \le 100\,000\)
- 모든 크기는 \(0\) 이상 \(10^9\) 이하의 정수이다.
입력 형식
첫째 줄에 상자의 수 \(N\)이 주어진다.
둘째 줄에 상자의 크기 \(N\)개가 공백으로 구분되어 주어진다.
셋째 줄에 뚜껑의 크기 \(N\)개가 공백으로 구분되어 주어진다.
출력 형식
어긋남의 합의 최솟값을 출력한다. 답이 \(32\)비트 정수 범위를 넘을 수 있음에 주의하여라.
예제 1
입력
3
1 5 3
4 2 2
출력
3
설명
상자 \(1\)에 뚜껑 \(2\), 상자 \(3\)에 뚜껑 \(2\), 상자 \(5\)에 뚜껑 \(4\)를 짝지으면 어긋남이 \(1 + 1 + 1 = 3\)으로 최소이다.
예제 2
입력
2
10 20
20 10
출력
0
설명
크기가 같은 짝끼리 맞추면 어긋남의 합이 \(0\)이다.
힌트
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
힌트 1
로그인하고 잠금 해제 · 10 🪙
힌트 2
로그인하고 잠금 해제 · 20 🪙
문제 정보
riseoj 작성
출처 Original
태그