조건

A 와 B 에 들어있는 값들 중 A에 있는 값은 자기보다 작은 B의 값을 선택할수있다.
몇개를 선택할수 있는지 찾는 문제다.

1<=N,M<=20000

접근

각각 A와B에는 최대 2만개의 값을 가질수있고, 그냥 A보다 작은 B의 개수를 다 찾아주고 그렇게 값들을 다 찾아주려했는데 조건은 최대 2만이다 이렇게 되면 N제곱으로써 1억연산이 넘어가게된다.

그래서 나는 다른 알고리즘을 써서 현재 자기가 들어가야할 위치를 찾아주는 방식을 생각했다.
그렇게 하기위해 B의 값들을 정렬해주고 시작했다
그리고 1 3 6 이되는데 여기서 최소는 0(인덱스) 최대는 2를 사용해서 최적의 자리를 찾아주었다

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T,N,M,temp;
int low,high,mid;
int ret;

vector<int> q;
vector<int> p;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> T;
    
    for(int i=0;i<T;i++) {
        
        q.clear();
        p.clear();
        
        cin >> N >> M;
        
        for(int j=0;j<N;j++) {
            cin >> temp;
            q.push_back(temp);
        }
        
        for(int j=0;j<M;j++) {
            cin >> temp;
            p.push_back(temp);
        }
        
        sort(q.begin(), q.end());
        sort(p.begin(), p.end());
        ret=0;
        
        for(int a:q) {
            
            low=0;
            high=M-1;
                
            while(low<=high) {
                mid=(low+high)/2;
                
                if(p[mid]<a) {
                    low=mid+1;
                }
                else {
                    high=mid-1;
                }
            }
            ret+=low;
        }
        
        cout << ret << "\n";
    }
    
    
}