7263 : 이분탐색 종합 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수 배열과 목표값 $T$가 주어질 때, 두 원소의 합이 $T$에 가장 가까운 합을 구하십시오.
배열을 정렬한 후 투 포인터 또는 이분탐색을 활용하여 최적의 쌍을 탐색합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
배열을 정렬한 후 투 포인터 또는 이분탐색을 활용하여 최적의 쌍을 탐색합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$과 목표 합 $T$가 주어집니다. ($2 \le N \le 100{,}000$, $|T| \le 10^9$)
둘째 줄에 $N$개의 정수가 주어집니다.
둘째 줄에 $N$개의 정수가 주어집니다.
출력 설명
두 원소의 합이 $T$에 가장 가까운 합을 출력합니다. 합이 같다면 더 작은 값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 9
1 3 5 7 9
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8도움
정렬 후 좌우 포인터를 이용합니다. 합이 $T$보다 크면 오른쪽 포인터를 줄이고, 작으면 왼쪽 포인터를 늘립니다. 매 단계에서 최선의 합을 기록합니다.