[백준] 7795 먹을 것인가 먹힐 것인가(C++)

 

문제 URL:

7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net)

7795번: 먹을 것인가 먹힐 것인가

심해에는 두 종류의 생명체 A와 B가 존재하는데 A는 B를 먹는다. 이때 A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하자.

 

이 문제는 이분 탐색을 이용하여 푸는 문제로 배열 A와 B를 정렬한 뒤 모든 A의 원소들에 대해서 이분탐색을 시행한다.

어떤 A의 원소에 대하여 A의 원소가 B의 원소 이하가 되는 index 지점을 찾게 된다면 생명체 A는 해당 index지점까지 B생명체를 먹을 수 있다. 따라서 쌍의 개수를 저장하는 변수 ans에 index를 더해주고 다음 A의 원소에 대해 이분 탐색을 시행한다. 

---

#include <iostream>
#include <algorithm>
using namespace std;

int t, n, m;
int A[20001], B[20001];

int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=0; i<n; i++)
            cin >> A[i];
        for(int i=0; i<m; i++)
            cin >> B[i];
        
        sort(A, A+n);
        sort(B, B+m);

        int ans = 0, low = 0;
		for(int i = 0; i < n; i++){
			int  high = m -1, mid;
            
			while(low <= high){
				mid = (low + high) / 2;
				if (B[mid] < A[i])
					low = mid + 1;
				else
					high = mid - 1;
			}
			ans += low;
		}
		cout << ans << '\n';
		ans = 0;
    }
}