HDOJ 1025 Constructing Roads In JGShining’s Kingdom

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
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;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDOJ 1025 Constructing Roads In JGShining’s Kingdom》有313个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注