16566 카드게임
알고리즘(이분탐색, 정렬, 분리집합, 세그먼트트리?)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1. 고른 카드를 버킷정렬함(400만개이므로 버킷정렬이 훨씬 빠르다. sort는 NlogN)
2. 범위를 저장하는 set<pair<int,int>>을 선언하고 첫 범위를 넣음(0-m)
3. 철수가 뽑은 카드의 수가 저장된 범위의 끝의 수보다 작을 때의 범위를 찾고, 그 범위안에서 uppper_bound로 큰수를 찾고,
그 찾은 공간을 제외한 양쪽의 두 범위를 다시 범위set에 추가하고, 현재 범위는 삭제한다.
ex) 철수가 뽑은 수 5 / 범위 : 0-3 5-7 / cards : 1 2 3 4 5 6 7 8
1. 범위 앞에서부터 검사
0-3 -> 3번째 카드는 4. 5보다 작으므로 통과
5-7 -> 7번째 카드는 8. 5보다 크므로 스탑
2. 5-7을 기준으로 upper_bound를 실시 : upper_bound(cards + (*iter).first, cards + (*iter).second + 1, 5);
-> 나온 포인터를 저장
3. 5-7에서 5보다 큰 것은 6이므로, 포인터는 card + 5를 가리키고 있음.
이 cards + 5를 기준으로 두 범위로 분리시킨 후 저장.
-> 이때 첫번째 원소이므로 왼쪽은 없음 따라서 오른쪽범위만 추가(6-7)
4. 기존 5-7범위는 삭제.
5. 찾은 수, 6을 리턴.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#define MAX_CARD 4000000
#define MAX_DRAW 10000
using namespace std;
int cards[MAX_CARD], draw[MAX_DRAW], numOfCard, m, numOfDraw;
bool buket[MAX_CARD + 1];
set<pair<int, int>> bound;
void buketSort();
int findCard(int drawCard);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> numOfCard >> m >> numOfDraw;
for (int i = 0; i < m; i++) {
int temp;
cin >> temp;
buket[temp] = true;
}
for (int i = 0; i < numOfDraw; i++) {
cin >> draw[i];
}
buketSort();
bound.insert(make_pair(0, m-1));
for (int i = 0; i < numOfDraw; i++)
cout << findCard(draw[i])<< "\n";
}
void buketSort() {
int index = 0;
for (int i = 1; i < MAX_CARD + 1; i++)
if (buket[i]) {
cards[index++] = i;
}
}
int findCard(int drawCard) {
for (set<pair<int, int>>::iterator iter = bound.begin(); iter != bound.end(); iter++) {
if (cards[(*iter).second] > drawCard) {
int* temp = upper_bound(cards + (*iter).first, cards + (*iter).second + 1, drawCard);
if(temp -cards != (*iter).first)
bound.insert(make_pair((*iter).first, temp - cards - 1));
if(temp - cards != (*iter).second)
bound.insert(make_pair(temp - cards + 1, (*iter).second));
bound.erase(iter);
return *temp;
}
}
}