먹을 것인가 먹힐 것인가

투포인터 문제임.

투포인터가 뭔지는 모름.

이렇게 풀었는데 당연히 런타임 에러남.

답은 이분탐색 lower_bound를 통해 값을 더해주면된다.

lower_bound는 이분탐색으로 통해서 값이나 idx값을 return하는데

없는 값을 탐색할 경우 가장 근접한 곳을 return 한다.

vector<int> c;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	c.push_back(1);
	c.push_back(3);
	c.push_back(3);
	c.push_back(4);
	c.push_back(4);

	auto pos = lower_bound(c.begin(), c.end(), 2);
	cout << pos - c.begin() << endl;
}

위와 같은 경우 1을 출력한다. 인덱스가 값 반환

vector<int> c;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	c.push_back(1);
	c.push_back(3);
	c.push_back(3);
	c.push_back(4);
	c.push_back(4);

	auto pos = lower_bound(c.begin(), c.end(), 3);
	cout << *pos << endl;
}

이라믄 값반환을 한다.

정렬하고 난뒤에 값이 이하인 부분을 찾아서 인덱스만큼 다 더해주면된다.

cpp코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <math.h>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"
#define ll long long

int t, n, m;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> t;
	while (t--)
	{
		int ret = 0;
		cin >> n >> m;
		vector<int> a(n), 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());
		for (int i = 0; i < n; ++i)
		{
			auto pos = lower_bound(b.begin(), b.end(), a[i]);
			ret += (int)(pos  - b.begin());
		}
		cout << ret << endl;
	}

	return 0;
}