백준 7795번 먹을 것인가 먹힐 것인가 ( C++ )

문제

https://www.acmicpc.net/problem/7795

 

해설

이분탐색 문제

이분탐색을 구현하는것보다 lower_bound or upper_bound를 사용하는것이 빠름

코드

#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
typedef long long ll;
 
int n,m,num;
ll ret, t;
 
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
 
  cin >> t;
  while(t){
    t--;
    cin >> n >> m;
    ret = 0;
    vector<int> a,b;
    for(int i=0;i<n;i++){
      cin >> num;
      a.push_back(num);
    }
    for(int i=0;i<m;i++){
      cin >> num;
      b.push_back(num);
    }
    sort(b.begin(),b.end());
 
    int start = 0;
    for(int i : a){
      auto tmp = (lower_bound(b.begin(),b.end(),i));
      ret += (int)(tmp - b.begin());
    }
 
    cout << ret<<"\n";
  }
}