题目
题目描述
Garfield听说OI班有N头神牛，每头神牛有两个属性，算法能力和思维能力，分别以Ai和Bi表示。如果神牛i和神牛j满足Ai ≥ Aj且Bi ≤ Bj，那么两位神牛会互相膜拜。Garfield认为膜拜是不和谐的，所以她想知道，最大的不存在膜拜关系的子集大小。
输入
第一行，一个整数N，表示神牛数量。
接下来N行，每行两个整数Ai和Bi，表示神牛的算法能力和思维能力。
接下来N行，每行两个整数Ai和Bi，表示神牛的算法能力和思维能力。
输出
一个整数，表示最大的子集大小。
输入样例复制
3
1 1
2 3
3 2
输出样例复制
2
说明
数据规模
对于40%的数据，N ≤ 103，
对于100%的数据，N ≤ 105。
对于40%的数据，N ≤ 103，
对于100%的数据，N ≤ 105。
分析
-
一眼排序然后求最长序列？？
- 相等的排序处理好就行了
代码
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 struct sb 6 { 7 int a,b; 8 }t[1000010]; 9 int d[1000010]; 10 bool cmp(sb a,sb b) 11 { 12 if (a.a>b.a) return true; 13 if (a.a==b.a) 14 if (a.b<b.b) return true; 15 return false; 16 } 17 bool cmpp(int a,int b) 18 { 19 return a>=b; 20 } 21 int ans; 22 int main () 23 { 24 int n; 25 cin>>n; 26 for (int i=1;i<=n;i++) 27 cin>>t[i].a>>t[i].b; 28 sort(t+1,t+1+n,cmp); 29 d[1]=t[1].b; 30 int len=1; 31 for (int i=2;i<=n;i++) 32 { 33 if (t[i].b<d[len]) d[++len]=t[i].b; 34 else 35 { 36 int wz=upper_bound(d+1,d+1+len,t[i].b,cmpp)-d; 37 d[wz]=t[i].b; 38 } 39 } 40 ans=max(ans,len); 41 cout<<ans; 42 }