jzoj1382 区间

题目大意

链接
有n个区间，用l,r描述，求一个最长的序列k，使第k个区间被第k-1个序列包含，第k-1个序列被第k-2个序列包含……。

解题思路

最长不下降子序列，考场上脑抽忘记写法然后写挂了。
先按右端点从大到小排，右端点相同就按左端点从小到大排。如果这个区间能够被当前的第tot个区间包含，就设它为第tot+1个区间，反之就去找能包含它的第k个区间，将第k+1个区间取代（要用二分）。最后输出tot。至于它为什么是正确的，可以去看最长不下降子序列的教程或自己画图理解。

代码

#include
using namespace std;
struct node{
	int x,y;
}a[100005];
int n,tot,d[100005];
bool cmp(node x,node y)
{
	if(x.x==y.x) return x.y>y.y;
	else return x.x<y.x;
}
int ef(int x)
{
	int l=1,r=tot;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(d[mid]>=x) l=mid+1;
		else r=mid;
	}
	return r;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1,cmp);
	d[0]=1e9;
	for(int i=1;i<=n;i++)
	{
		if(a[i].y<=d[tot]) d[++tot]=a[i].y;
		else d[ef(a[i].y)]=a[i].y;
	}
	cout<<tot;
	return 0;
}
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