当前位置：网站首页>【集训DAY3】 Section【贪心】【二分】

【集训DAY3】 Section【贪心】【二分】

2022-07-15 18:16:00 【VL——MOESR】

在这里插入图片描述

思路：

先把左端点排序，然后右端点做最长不上升子序列

$c o d e$

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 10;

int n, tot, b[MAXN];

struct node {
    
	int x, y;
}a[MAXN];

bool cmp(node x, node y) {
    
	if(x.x!=y.x) return x.x < y.x;
	else return x.y > y.y;
}

int Find(int x) {
    
	int l=1, r=tot, ans = 1e9;
	while(l <= r) {
    
		int mid = l + r >> 1;
		if(b[mid] < x) r = mid - 1, ans = min(ans, mid);
		else l = mid + 1;
	}
	return ans;
}

int main() {
    
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
		scanf("%d%d", &a[i].x, &a[i].y);
	sort(a+1, a+1+n, cmp);
	tot = 1, b[1] = a[1].y;
	for(int i = 2; i <= n; i ++) {
    
		if(a[i].y <= b[tot]) b[++tot] = a[i].y;
		else {
    
			int k = Find(a[i].y);
			b[k] = a[i].y;
		}
	}
	printf("%d", tot);
	return 0;
}