2568 전기줄
알고리즘(LIS)
1
2
1. LIS를 구하면 그것들이 겹치지 않고 최대로 연결가능한 전깃줄들이다.
2. 따라서 LIS를 구하고 전체 전깃줄에서 LIS를 빼면 빼야하는 전깃줄의 수와 전깃줄의 종류가 나오게 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#define MAX_WIRE 100001
using namespace std;
struct Wire {
int a;
int b;
bool check;
bool operator <(Wire s) {
return a < s.a;
}
};
Wire wire[MAX_WIRE];
int numOfWire, length[500001], save[500001], numOfSave;
void LIS();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> numOfWire;
for (int i = 0; i < numOfWire; i++)
cin >> wire[i].a >> wire[i].b;
sort(wire, wire + numOfWire);
LIS();
}
void LIS() {
int result = 0, index = 0;
for (int i = 0; i < numOfWire; i++) {
int *lb = lower_bound(save, save + numOfSave, wire[i].b);
length[wire[i].a] = lb - save + 1;
*lb = wire[i].b;
if (length[wire[i].a] == numOfSave + 1)
numOfSave++;
if (result < length[wire[i].a]) {
result = length[wire[i].a];
index = i;
}
}
cout << numOfWire - result << "\n";
for (int i = index; i >= 0; i--) {
if (result <= 0)
break;
if (length[wire[i].a] == result) {
wire[i].check = true;
result--;
}
}
for (int i = 0; i < numOfWire; i++)
if (!wire[i].check)
cout << wire[i].a << "\n";
}