높이가 h 이상인 나무판에 대해 남는 여부를 결정했다면 해당 나무판들은 최종적으로 남아있을 수 있다.
높이가 h 미만인 나무판들로 어떠한 울타리를 만들어도 높이가 h 이상인 나무판을 포함할 수 없기 때문이다.
그러므로 다음의 그리디 알고리즘이 가능하다.
1. 현재 남아있을지 결정해야 하는 나무판들의 높이 중 최댓값을 h라 한다.
2. 높이가 h인 나무판들에 대해 이미 남아 있기로 결정된 h보다 큰 나무판과 겹치는 부분을 제거한다. 높이가 h인 각 나무판마다 제거되지 않은 부분의 x 성분 최솟값을 si, 최댓값을 ei 라 하자.
3. i < j일 때 si < sj & ei < ej를 만족하도록 높이가 h인 나무판들을 최대한 많이 선별한다.
4. 선별된 나무판들을 최종적으로 남도록 결정한다.
5. 결정하지 못한 나무판들에 대해 1로 돌아가 처리한다.
2, 3번 과정은 map으로 처리 가능하다. 자세한 구현은 아래 소스를 참고하자.
시간복잡도는 $O(n\lg n)$
#include<cstdio> #include<map> #include<vector> #include<algorithm> using namespace std; int n; struct st { int x, w, h, idx; }a[100000]; vector<int> res; vector<pair<int, int> > stk; map<int, int> mp; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].h), a[i].idx = i + 1; sort(a, a + n, [](st i, st j) {return i.h > j.h || i.h == j.h&&i.x < j.x; }); for (int i = 0, s, e; i < n; i++) { auto it = mp.upper_bound(s = a[i].x); if (it != mp.begin() && s < (--it)->second) s = it->second; it = mp.upper_bound(e = a[i].x + a[i].w); if (it != mp.begin() && e <= (--it)->second) e = it->first; if (s < e && (stk.empty() || stk.back().second < e)) { while (!stk.empty() && stk.back().first == s) stk.pop_back(), res.pop_back(); stk.push_back({ s,e }); res.push_back(a[i].idx); } if (i == n - 1 || a[i].h^a[i + 1].h) { while (!stk.empty()) { s = stk.back().first; e = stk.back().second; it = mp.upper_bound(s); if (it != mp.begin() && s == prev(it, 1)->second) s = (--it)->first; while (it != mp.end() && it->first <= e) { e = max(e, it->second); mp.erase(it++); } mp[s] = e; stk.pop_back(); } } } printf("%d\n", res.size()); for (auto it : res) printf("%d ", it); return 0; }
