[2568] 전깃줄 - 2

https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

<문제>

잘 생각해보면 아래와 같은 문제라고 할 수 있다.

-> 가장 긴 증가하는 부분수열의 최적해 + 최적해역추적

N이 10만이고, 시간제한이 1초이므로 O(NlogN)으로 구현해야 한다. 결국 아래문제와 같은 문제라는걸 알 수 있다.

https://www.acmicpc.net/problem/14003 

14003번: 가장 긴 증가하는 부분 수열 5

<소스코드>

#include <stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
int main() {
    int i, j;
    scanf("%d", &n);
    vector<pair<int, int> >v(n);
    for (i = 0; i < n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    
    vector<int> stk;
    vector<pair<int,int>> path;
    for (i = 0; i < n; i++) {
        if (stk.empty() || stk.back() < v[i].second) {
            path.push_back({ stk.size(), v[i].first });
            stk.push_back(v[i].second);
        }
        else {
            auto iter = lower_bound(stk.begin(), stk.end(), v[i].second);
            *iter = v[i].second;
            path.push_back({ iter - stk.begin(), v[i].first });
        }
    }
    vector<int> ans;
    for (i = path.size() - 1, j = stk.size() - 1; i >= 0; i--) {
        if (path[i].first == j) j--;
        else ans.push_back(path[i].second);
    }
    sort(ans.begin(), ans.end());
    printf("%d\n", ans.size());
    for (auto i : ans)
        printf("%d\n", i);
    return 0;
}