7795번_먹을 것인가 먹힐 것인가_BOJ

문제 링크

7795번 먹을 것인가 먹힐 것인가 : https://www.acmicpc.net/problem/7795

문제 설명 및 해결 아이디어

lower_bound를 이용하여 x라는 값을 찾으면, x보다 크거나 같은 값중 최소값의 위치를 return해준다. 이 아이디어를 이용하여 문제를 풀 수 있다.

코드

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