[HDU] 1025 Constructing Roads In JGShining's Kingdom - 二分的求最大递增非连续子序列-白红宇

[HDU] 1025 Constructing Roads In JGShining's Kingdom - 二分的求最大递增非连续子序列

阅读量：4924 次

发布时间：2019-06-11

本文共 910 字，大约阅读时间需要 3 分钟。

题目链接：

方法：求最大递增非连续子序列朴素的方法是o(n^2)的时间复杂度，而该题要超时，所以用二分的，具体实现参见链接

感想：熟悉上述链接的定理证明。

代码：

View Code

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int const MAX =0x3f3f3f3f;struct Road{    int p;    int r;};bool cmp(Road x,Road y){    if(x.p < y.p )        return true;    return false;}Road roads[500001];int counts[500001];int main(){    int n=0,tc=1;    while(scanf("%d",&n)!=EOF)    {        memset(counts,0,sizeof(counts));        for(int i=0;i
          
           =roads[i].r)                    ed = mid-1;                else                    p=mid+1;            }            counts[p]=roads[i].r;            if(p>len)len++;        }        cout<<"Case "<
           
            <<":"<
            
             1) cout<<"My king, at most "<
             
              <<" roads can be built."<