本文主要是介绍膜拜神牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
Garfield听说OI班有N头神牛，每头神牛有两个属性，算法能力和思维能力，分别以Ai和Bi表示。如果神牛i和神牛j满足Ai ≥ Aj且Bi ≤ Bj，那么两位神牛会互相膜拜。Garfield认为膜拜是不和谐的，所以她想知道，最大的不存在膜拜关系的子集大小。
输入
第一行，一个整数N，表示神牛数量。
接下来N行，每行两个整数Ai和Bi，表示神牛的算法能力和思维能力。
输出
一个整数，表示最大的子集大小。
输入样例
3
1 1
2 3
3 2
输出样例
2
说明
数据规模
对于40%的数据，N ≤ 103，
对于100%的数据，N ≤ 105。
.
.
.
.
.
分析
排序后可把问题转化为求最长下降子序列
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;struct edge
{int a,b;
}w[100010];int n,a[200000],ans=0,f[200000];bool cmp(edge x,edge y)
{if (x.a!=y.a) return x.a>y.a; else return x.b>y.b;
}void lds()
{memset(f,127,sizeof(f));for (int i=1;i<=n;i++)if (a[i]<f[ans]){ans++;f[ans]=a[i];} else{int l=1,r=ans;while (l<r){int mid=(l+r)/2;if (f[mid]<=a[i]) r=mid; else l=mid+1;}f[l]=a[i];}
}int main()
{scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d",&w[i].a,&w[i].b);sort(w+1,w+n+1,cmp);for (int i=1;i<=n;i++)a[i]=w[i].b;lds();printf("%d",ans);return 0;
}
这篇关于膜拜神牛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
