https://www.acmicpc.net/problem/7795
어떤 a에 대하여 모든 b와 비교하는 것은 시간이 너무 오래 걸린다.
따라서 투포인터 방식을 이용했다.
먼저 a 배열과 b 배열을 오름차순 정렬하였다.
a와 b의 뒤에서부터 둘을 비교하는데, 이 둘의 인덱스를 i, j라 하자.
a[i] > b[j]인 경우
j 이하의 b의 원소는 모두 a[i]보다 작기 때문에, j 이하의 인덱스는 탐색할 필요가 없고, a[i]가 먹을 수 있는 b는 j+1개이다.
다음에 a[i-1]과 b[j]를 비교하면 된다.
a[i] <= b[j]인 경우
a[i]보다 작은 b의 원소를 찾기 위해 다음에 b[j-1]과 비교한다.
이렇게 i와 j를 이용하여 탐색하고, 답을 구하였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t, n, m;
cin >> t;
while(t--) {
cin >> n >> m;
vector<int> a(n);
vector<int> b(m);
for(int i=0; i<n; i++) cin >> a[i];
for(int i=0; i<m; i++) cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i=n-1, j=m-1, ans=0;
while(i>=0 && j>=0) {
if(a[i] > b[j]) {
ans += j+1;
i--;
} else {
j--;
}
}
cout << ans << "\n";
}
return 0;
}