티스토리 뷰

문제: 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)이 될 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13549 숨바꼭질3  (0) 2017.01.17
BOJ)2910 빈도 정렬  (1) 2017.01.15
BOJ)7795 먹을 것인가 먹힐 것인가  (0) 2017.01.15
BOJ)3758 KCPC  (0) 2017.01.15
BOJ)8983 사냥꾼  (0) 2017.01.15
BOJ)10277 JuQueen  (0) 2017.01.15
댓글
댓글쓰기 폼