[白俊]2568電線-2


白駿2568電線-2
  • https://www.acmicpc.net/problem/2568
  • を消す必要がある電線の最小数=電線全体の数-LISの長さ
  • を除去する必要がある電線の配列方法を見つける必要があります.そのため、LISを求めるときとは反対です.
    ->レコード配列の一番後ろからナビゲート
    ->レコード[i]に格納されているインデックスは連続降順ではありません.
    ->retベクトルはpush back(line[i].first)演算を行います.
  • #include <iostream>
    #include <limits.h>
    #include <algorithm>
    #include <vector>
    #include <utility>
    using namespace std;
    
    bool cmp(const pair<int, int> &a, const pair<int, int> &b){
    	return a.first < b.first;
    }
    
    int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    	cout.tie(NULL);
    
    	vector <pair<int, int>> line;
    
    	int n;
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		int left, right;
    		cin >> left >> right;
    		line.push_back(make_pair(left, right));
    	}
    	sort(line.begin(), line.end(), cmp);
    
    	vector <int> vt;
    	vector <int> record;
    	vector <int> ret;
    
    	// record 벡터에 line[i].second가 vt벡터에 저장되는 위치 저장 
    	int idx = 0;
    	vt.push_back(line[0].second);
    	record.push_back(0);
    
    	for (int i = 1; i < n; i++) {
    		if (vt.back() < line[i].second) {
    			vt.push_back(line[i].second);
    			record.push_back(++idx);
    		}
    		else {
    			auto it = lower_bound(vt.begin(), vt.end(), line[i].second);
    			*it = line[i].second;
    			record.push_back(it-vt.begin());
    		}
    	}
    
    	// lis가 아닌 값 추적
    	int flag = idx;
    	for (int i = n-1 ; i >= 0; i--) {
    		if (record[i] == flag) 
    			flag--;
    		else 
    			ret.push_back(line[i].first);
    	}
    	reverse(ret.begin(), ret.end());
    
    	//결과
    	cout << n - idx - 1<<"\n";
    	for (auto it = ret.begin(); it != ret.end(); it++)
    		cout << *it << "\n";
    
    	return 0;
    }