[백준 16566] 카드 게임

문제

www.acmicpc.net/problem/16566

16566번: 카드 게임

 

풀이

낼 수 있는 카드를 정렬해둔 후, upperbound를 통해 낼 카드 번호를 바로 구할 수 있을 것 같지만 낸 카드는 버리기에 사용한 카드의 유무를 저장하는 배열을 사용해 항상 사용하지 않은 카드를 내는 식으로 해결할 수 있습니다.  $O((m + k)logm)$

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, k, x, idx;
vector<int> v;
bool c[4000001];

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n >> m >> k;
	v.resize(m);
	for (int& i : v) cin >> i;
	sort(v.begin(), v.end());
	while (k--) {
		cin >> x;
		idx = upper_bound(v.begin(), v.end(), x) - v.begin();
		while (idx <= n && c[idx]) idx++;
		cout << v[idx] << "\n";
		c[idx] = 1;
	}
}