[白俊]2568電線-2
白駿2568電線-2 https://www.acmicpc.net/problem/2568 を消す必要がある電線の最小数=電線全体の数-LISの長さ を除去する必要がある電線の配列方法を見つける必要があります.そのため、LISを求めるときとは反対です.
->レコード配列の一番後ろからナビゲート
->レコード[i]に格納されているインデックスは連続降順ではありません.
->retベクトルはpush back(line[i].first)演算を行います.
->レコード配列の一番後ろからナビゲート
->レコード[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;
}
Reference
この問題について([白俊]2568電線-2), 我々は、より多くの情報をここで見つけました https://velog.io/@sunjoo9912/백준-2568-전깃줄-2テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol