7245 : Lower Bound
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
Lower Bound는 정렬된 배열에서 특정 값 $x$보다 크거나 같은 첫 번째 원소의 위치를 찾는 연산입니다.
주어진 $Q$개의 질의에 대해 각각의 Lower Bound를 0-based 인덱스로 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
주어진 $Q$개의 질의에 대해 각각의 Lower Bound를 0-based 인덱스로 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정렬된 정수 배열의 크기 $N$과 질의 개수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 질의 값 $x$가 공백으로 구분되어 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 질의 값 $x$가 공백으로 구분되어 주어집니다.
출력 설명
각 질의에 대해 $x$보다 크거나 같은 첫 번째 원소의 인덱스(0-based)를 한 줄에 출력합니다.
모든 원소가 $x$보다 작으면 $N$을 출력합니다.
모든 원소가 $x$보다 작으면 $N$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 4
1 3 5 7 9 11
0 5 6 12
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
2
3
6도움
Python의
bisect.bisect_left(arr, x)가 Lower Bound를 반환합니다. 직접 구현 시 while lo < hi: mid=(lo+hi)//2; if arr[mid] >= x: hi=mid; else: lo=mid+1를 사용합니다.