16566 ์นด๋๊ฒ์
์๊ณ ๋ฆฌ์ฆ(์ด๋ถํ์, ์ ๋ ฌ, ๋ถ๋ฆฌ์งํฉ, ์ธ๊ทธ๋จผํธํธ๋ฆฌ?)
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์ ๋ฆฌํด.
์ฝ๋
#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;
}
}
}