BOJ)7795 먹을 것인가 먹힐 것인가

문제: icpc.me/7795

A집합과 B집합이 주어졌을 때 A집합의 어떤 수 X가 B집합의 어떤 수 Y보다 큰 경우의 수의 합을 출력하는 문제이다.

A집합과 B집합의 크기 N M은 20000까지 들어올 수 있으니

O(N*M)의 방법으로 완전탐색한다면 한번의 테스트 케이스에서도 간당간당한데 여러번의 테스트 케이스를 거친다면 TLE를 보게 될 것이다. 

우리는 B집합을 정렬한 후 lower_bound를 이용하여 N개의 쿼리에서 각각 X보다 작은 수 Y의 개수를 구할 수 있다.

시간 복잡도는 O((N+M)logM)이 될 것이다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int t, n, m, x, res;
vector<int> a;
vector<int> b;
int main() {
    scanf("%d", &t);
    while (t--) {
        a.clear(), b.clear();
        res = 0;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n;i++){
            scanf("%d", &x);
            a.push_back(x);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            b.push_back(x);
        }
        sort(b.begin(), b.end());
        for (auto i : a) 
            res += lower_bound(b.begin(), b.end(), i) - b.begin();
        printf("%d\n", res);
    }
    return 0;
}