?題目： acdream 1216? Beautiful People

題意：每一個(gè)人有兩個(gè)值，能力值和潛力值，然后要求一個(gè)人的這兩個(gè)值都嚴(yán)格大于第二個(gè)人的時(shí)候，這兩個(gè)人才干呆在一塊兒，給出很多人的值，求最多有多少個(gè)人？

分析：非常easy想到是個(gè)單調(diào)非增模型，假設(shè)用O（n*n）的寫法的話，會(huì)超時(shí)！

那么我們就要用二分優(yōu)化來找。

我們能夠先按第一個(gè)值 x 從小到大排序，然后按第二個(gè)值從大到小排序，這種話找出的最長(zhǎng)個(gè)數(shù)是沒有錯(cuò)的。（想想為什么）

假如這樣一個(gè)例子：

5

1 10

2 12

3 5

3 1

4 3

6 7

首先dp數(shù)組僅僅有第一，二組例子：1 10 和2 12

然后第三個(gè)例子替換第一組：3 5 和 2 12 ?，看看這組例子，發(fā)現(xiàn)不滿足，可是他總的長(zhǎng)度不會(huì)變，可是這樣保存的話能保證后面出來的數(shù)可以最長(zhǎng)。所以要想辦法保存路徑

然后第四組例子替換第三組：3 1 和 2 12?

然后第5組例子替換第二組： 3 1 ?和 4 3 是不是滿足條件了，并且最大值值變的更小了，

然后第六組例子加在后面：3 1 和 4 3 和 6 7 ，最大值

最后全部值的二分搜索的值為：1 2 1 1 2 3?

那么發(fā)現(xiàn)保存路徑也簡(jiǎn)單了。

然后從這個(gè)值里面輸出一個(gè)遞減的初始數(shù)組標(biāo)號(hào)就能夠了、

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;
}