首页 > 代码库 > 二路单调自增子序列模型【acdream 1216】
二路单调自增子序列模型【acdream 1216】
题目:acdream 1216 Beautiful People
题意:每个人有两个值,能力值和潜力值,然后要求一个人的这两个值都严格大于第二个人的时候,这两个人才能呆在一块儿,给出许多人的值,求最多有多少个人?
分析:很容易想到是个单调非增模型,如果用O(n*n)的写法的话,会超时!
那么我们就要用二分优化来找。
我们可以先按第一个值 x 从小到大排序,然后按第二个值从大到小排序,这样的话找出的最长个数是没有错的。(想想为什么)
假如这样一个样例:
5
1 10
2 12
3 5
3 1
4 3
6 7
首先dp数组只有第一,二组样例:1 10 和2 12
然后第三个样例替换第一组:3 5 和 2 12 ,看看这组样例,发现不满足,但是他总的长度不会变,但是这样保存的话能保证后面出来的数能够最长。所以要想办法保存路径
然后第四组样例替换第三组:3 1 和 2 12
然后第5组样例替换第二组: 3 1 和 4 3 是不是满足条件了,而且最大值值变的更小了,
然后第六组样例加在后面:3 1 和 4 3 和 6 7 ,最大值
最后所有值的二分搜索的值为:1 2 1 1 2 3
那么发现保存路径也简单了。
然后从这个值里面输出一个递减的初始数组标号就可以了、
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <iostream> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int N = 110000; struct Node { int x,y; int num,count; }; Node a[N]; int cmp(Node a,Node b) { if(a.x!=b.x) return a.x<b.x; if(a.y!=b.y) return a.y>b.y; } int dp[N],mark[N]; int Bin_Search(int l,int r,int x) { while(l<=r) { int mid = (l+r)/2; //假如要求相等的情况下,返回较小的值。 if(dp[mid]==x) return mid; else if(dp[mid]<=x) l=mid+1; else r=mid-1; } return l; } int main() { int n; while(~scanf("%d",&n)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].num=i; } sort(a+1,a+n+1,cmp); memset(dp,0x3f3f3f3f,sizeof(dp)); int ans=0; int len = 1; for(int i=1;i<=n;i++) { int tmp=Bin_Search(1,len,a[i].y); //lower_bound(dp+1,dp+1+n,a[i].y)-dp; if(tmp==len) len++; dp[tmp] = a[i].y; mark[i] = tmp; ans = max(ans,tmp); } printf("%d\n",ans); for(int i=n;i>=1;i--) { //printf("xx%d ",mark[i]); if(mark[i]==ans) { printf("%d",a[i].num); if(ans!=1) printf(" "); ans--; } } printf("\n"); } return 0; }
二路单调自增子序列模型【acdream 1216】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。