[백준] 7795 먹을 것인가 먹힐 것인가 c++

이분탐색을 생각 못했고 그냥 완전 탐색하면 되는거 아닌가 했었다.

태그 안보고 푸는 연습을 해야될 것 같다.

A와 B를  정렬하고

A벡터의 각 자리의 값하고 같아지는 B의 인덱스를 구하고 ans를 더해주면 된다.

A보다 작은 것의 개수를 구하는 것인데 벡터가 0부터 시작하기 때문에 인덱스를 더해주면된다.

A의 매 자리 마다 low를 0으로 초기화 해주는 것하고 low를 그대로 두는 것하고 시간 차이가 난다.

A의 i+1자리에 있는 수는 i에 있는 수보다 크기 때문에,

A[i]에서 구한  low 인덱스보다 작거나 같은 인덱스에 있는 B의 수는 항상 A[i+1]보다 작다.

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

7795번: 먹을 것인가 먹힐 것인가

 

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


using namespace std;

int main()
{
	int T;
	int N, M,temp;
	cin >> T;
	while (T--) {
		
		cin >> N >> M;
		vector<int>A;
		vector<int>B;
		for (int i = 0; i < N; i++)
		{
			cin >> temp;
			A.push_back(temp);
		}

		for (int i = 0; i < M; i++)
		{
			cin >> temp;
			B.push_back(temp);
		}
		sort(A.begin(), A.end());
		sort(B.begin(), B.end());
		
		int ans = 0;
		int low = 0;
		for (int i = 0; i < N; i++) {
			int  high = B.size() -1, mid;
			while (low <= high)
			{
				mid = (low + high) / 2;
				if (B[mid] < A[i])
				{
					low = mid + 1;
				}
				else 
				{
					high = mid - 1;
				}
				
			}
			ans += (low);
		
		}
		cout << ans << endl;
		ans = 0;

	}
}