luogu 阅读链接。
题意
题目链接
有两行，一行 n 个点，和 m 条线（从第一行的节点连向第二行的节点）。
现在问你最多留下多少线，能使任意两条线均不相交。
思路
为了方便描述，第 a 条线的第一行节点是 ax，第二行节点是 ay。
显然，两条相交的线 a,b 必然满足，ax<bx∧ay>by 或是 ax=ax∨ay=by。
那么我们对 ax 做升序，相等时 ay 做降序（规避第二种情况）。
这样我们只需要对 ay 求最长上升子序列即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int N = 1e6 + 10;
struct A{int x, y;}a[N];
int f[N], tot, n, m;
int find(int x){
int l = 0, r = tot;
while(l < r){
int mid = (l + r) >> 1;
if(f[mid] < x)l = mid + 1;
else r = mid;
}
return l;
}
int32_t main(){
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + 1 + m, [](A&i, A&j){return (i.x ^ j.x) ? (i.x < j.x) : (i.y > j.y);});
f[tot = 1] = a[1].y;
for(int i = 1; i <= m; i++){
if(a[i].y > f[tot])f[++tot] = a[i].y;
else f[find(a[i].y)] = a[i].y;
}
cout << tot << endl;
return 0;
}
|
