二路单调自增子序列模型【acdream 1216】

傷城~ 2022-08-12 21:29 27阅读 0赞

题目：[acdream 1216 Beautiful People][]

题意：每个人有两个值，能力值和潜力值，然后要求一个人的这两个值都严格大于第二个人的时候，这两个人才能呆在一块儿，给出许多人的值，求最多有多少个人？

分析：很容易想到是个单调非增模型，如果用O（n\*n）的写法的话，会超时！

那么我们就要用二分优化来找。

我们可以先按第一个值 x 从小到大排序，然后按第二个值从大到小排序，这样的话找出的最长个数是没有错的。（想想为什么）

假如这样一个样例：

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 Beautiful People]: http://acdream.info/problem?pid=1216