1628번 - 수 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 369 | 129 | 87 | 46.524% |
문제
음 아닌 정수들로 이루어진 두 개의 집합 S와 T가 있다. S의 원소들과 T의 원소들을 짝지으려고 하는데, 다음과 같은 규칙을 만족하도록 하고 싶다.
- S의 임의의 원소 s는 T의 어떤 원소와도 짝지어질 수 있다. 또한 T의 임의의 원소 t도 S의 어떤 원소와도 짝지어질 수 있다.
- S의 모든 원소는 적어도 하나의 T의 원소와는 짝지어져야 하고, T의 모든 원소 역시 적어도 하나의 S의 원소와는 짝지어져야 한다.
예를 들어 S={2, 8, 9, 10, 11}, T={0, 3, 4, 6, 7, 11}을 보자. {(2, 0), (2, 3), (2, 4), (8, 6), (9, 7), (10, 11), (11, 11)}은 규칙을 만족하는 경우가 된다. 하지만 {(2, 0), (8, 3), (9, 4), (10, 6), (11, 7)}은 규칙을 만족하는 경우가 아닌데, T의 원소 11이 S의 어떤 원소와도 짝지어지지 않았기 때문이다.
각각의 짝 (a, b)의 비용이란, a와 b의 차이의 절댓값으로 정의된다. 우리는 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지으려 한다. 위에서 주어진 S와 T에 대해서는 10이 최소의 비용합이 된다.
S와 T가 주어지면, 모든 비용의 합을 최소로 하도록 S의 원소들과 T의 원소들을 짝지어 주는 프로그램을 작성하시오.
입력
첫째 줄에 S의 원소의 개수와 T의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 S의 원소, 셋째 줄에는 T의 원소가 첫째 줄에 주어진 개수만큼 빈 칸을 사이에 두고 증가하는 순서대로 주어진다. 각 집합의 원소의 크기는 50,000 이하의 자연수이며, 주어지는 수는 0 이상 100,000 이하의 정수이다.
출력
첫째 줄에 최소의 비용합을 출력한다.
예제 입력 1
5 6 2 8 9 10 11 0 3 4 6 7 11
예제 출력 1
10
출처
ICPC > Regionals > Asia Pacific > Korea > Asia Regional - Seoul 2007 J번
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호