HDOJ 1025 Constructing Roads In JGShining's Kingdom

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1025

题意：河两岸各有n各点，编号从左到右都依次为1~n，已知它们与对岸某点能先连，若不能相交，最多能连几点。

仔细分析题目，可以联系到LIS。

因为数据量较大，所以用LIS的Nlog(N)的方法做。

LIS算法详细讲解见：http://www.wutianqi.com/?p=1850

#include 
using namespace std;

int p[500005], b[500005];
int n;

int bSearch(int num, int k)  
{  
    int low=1, high=k;  
    while(low<=high)  
    {  
        int mid=(low+high)/2;  
        if(num>=b[mid])  
            low=mid+1;  
        else   
            high=mid-1;  
    }  
    return low;  
}  

int LIS()
{
    int low = 1, high = n;
    int k = 1;
    b[1] = p[1];
    for(int i=2; i<=n; ++i)
    {
        if(p[i]>=b[k])
            b[++k] = p[i];
        else
        {
            int pos = bSearch(p[i], k);
            b[pos] = p[i];
        }
    }
    return k;
}

int main()
{
    int a, b;
    int nCases = 1;
    while(scanf("%d", &n;) != EOF)
    {
        for(int i=1; i<=n; ++i)
        {
            scanf("%d %d", &a;, &b;);
            p[a] = b;
        }
        int ans = LIS();
        printf("Case %d:\nMy king, at most %d road", nCases++, ans);
        if(ans != 1) printf("s");
        printf(" can be built.\n\n");
    }
    return 0;
}