10775 airport
์๊ณ ๋ฆฌ์ฆ(์๋ฃ๊ตฌ์กฐ, ํธ๋ฆฌ๋ฅผ ์ด์ฉํ ์ด์งํ์)
1. ๊ฒ์ดํธ์ ๊ฐ์์ ๋ง๊ฒ 1~G๋ฅผ set์ ๋ฃ์
2. boolํ check ๋ฐฐ์ด์์, gi์ ์๋ฌด๊ฒ๋ ์์ผ๋ฉด gi์ ๋ฃ๊ณ set์์ gi ์ญ์
3. ์ด๋ฏธ gi์ ๋ค์ด๊ฐ ์์ผ๋ฉด, set์์ upperbound๋ก gi์ด๊ณผํ๋ ์ฒซ๋ฒ์งธ๋ฅผ ์ฐพ์
-> ๋ง์ฝ ๊ทธ ์ฒซ๋ฒ์งธ๊ฐ begin()์ด๋ฉด ์๋ ๊ฒ -> false ๋ฐํ ํ ์
๋ ฅ ์ข
๋ฃ
-> begin()์ด ์๋๋ฉด ๊ทธ ๊ณณ์์ ํ์นธ ์๋์ ๋ํนํ๊ณ , true๋ฐํ
์ฃผ์์
1. set์ erase๋ iterator๋ฅผ ๋ฐ๋๋ค.
์ฝ๋
#include <iostream>
#include <set>
#define MAX 100001
using namespace std;
int numOfGate, numOfPlane, planeCount;
bool gate[MAX];
set<int> s;
//gateIndex์ ๋ฃ์ ์๋ฆฌ์ ๋ฃ๊ธฐ
//๋ฃ์ ๊ณณ์ ์ต๋ํ ํฐ ๊ณณ์ ๋ฃ๋๊ฒ ์ข๋ค.
//๋ฐ๋ผ์ 5๊ฐ ๋ค์ด์ค๋ฉด, gateIndex์์ 5๋ฅผ ์กฐํํด์, ๊ฐ๋ฆฌํค๋ ์์น์ ๋ฃ๊ธฐ
//๊ฐ๋ฆฌํค๋ ์์น๋ ์ฒ์์ ์๊ธฐ์์ , ๊ทธ ํ์ ๋ฃ์ด์ง๋๋ง๋ค 1์นธ์ฉ ์์ผ๋ก ๋น๊ธฐ๊ธฐ.
//๋์ ๊ทธ ์์ ๊ฒ๋ ์ ์ ํ ์กฐ์
//ex) 5 5 5 ๊ณ์ ๋ค์ด์ค๋ฉด, gateIndex๋ 1 2 3 4 5 6 -> 1 2 3 4 4 6-> 1 2 3 3 3 6-> 1 2 2 2 2 6-> 1 1 1 1 1 6-> 0 0 0 0 0 6-> 0์๋ฆฌ์ ๋ชป๋ฃ๊ฒ ํจ.
//1์ฉ ์ค์ฌ์ฃผ๋๊ณผ์ ์์ ์๊ฐ์ด๊ณผ๊ฐ ๋ธ.
bool canPut(int max);
void makeSet();
int main() {
cin >> numOfGate >> numOfPlane;
makeSet();
int temp;
bool check = true;
for (int i = 0; i < numOfPlane; i++) {
cin >> temp;
if (check && canPut(temp))
planeCount++;
else
check = false;
}
cout << planeCount << endl;
}
void makeSet() {
for (int i = 1; i <= numOfGate; i++)
s.insert(i);
}
bool canPut(int max) {
if (!gate[max]) {
gate[max] = true;
s.erase(s.find(max));
return true;
}
else {
set<int>::iterator iter = s.upper_bound(max);
if (iter == s.begin())
return false;
else {
iter--;
gate[*iter] = true;
s.erase(iter);
return true;
}
}
}