7251 : 두 배열 K번째
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정렬된 두 배열 $A$와 $B$를 합쳐 정렬했을 때 $K$번째 원소의 값을 구하십시오.
이분탐색을 이용하면 $O(\log(\min(N, M)))$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
이분탐색을 이용하면 $O(\log(\min(N, M)))$ 시간에 해결할 수 있습니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열 $A$, $B$의 크기 $N$, $M$과 정수 $K$가 주어집니다. ($1 \le K \le N+M \le 200{,}000$)
둘째 줄에 오름차순 정렬된 배열 $A$가 주어집니다.
셋째 줄에 오름차순 정렬된 배열 $B$가 주어집니다.
둘째 줄에 오름차순 정렬된 배열 $A$가 주어집니다.
셋째 줄에 오름차순 정렬된 배열 $B$가 주어집니다.
출력 설명
두 배열을 합쳐 정렬했을 때 $K$번째로 위치하는 원소의 값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 4 4
1 3 5
2 4 6 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
두 배열을 합병하여 정렬한 후 $K$번째 원소를 반환하는 단순한 방법은 $O((N+M)\log(N+M))$입니다. 더 효율적인 방법은 이분탐색을 이용하여 각 배열에서 몇 개를 취할지 결정합니다.