这道题我提交了好几次才过的,主要的因为TLE,因为我的算法效率是O(n^2),在网上找到了更高效的是O(n*logn).在这里我附上我两种代码.
Code
#include<iostream>
#include<algorithm>
usingnamespacestd;
structnode
{
intp;
intr;
};
nodeR[500000];
boolcomp(nodea,nodeb)
{
if(a.p!=b.p)
returna.p<b.p;
else
returna.r<b.r;
}
intb[500000];
intmain()
{
intn,i,j,max,k=0;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
b[i]=1;
}
for(i=0;i<n;i++)
{
scanf("%d%d",&R[i].p,&R[i].r);
}
sort(R,R+n,comp);
max=b[0];
for(i=1;i<n;i++)
{
for(j=0;j<i;j++)
{
if(R[j].p<R[i].p&&R[j].r<R[i].r&&b[i]<b[j]+1)
{
b[i]=b[j]+1;
}
if(b[i]>max)
{
max=b[i];
}
}
}
++k;
if(max>1)
printf("Case%d:\nMyking,atmost%droadscanbebuilt.\n\n",k,max);
else
printf("Case%d:\nMyking,atmost%droadcanbebuilt.\n\n",k,max);
}
return0;
}
AC代码:
Code
#include<iostream>
usingnamespacestd;
constintMax=500001;
introad[Max],dp[Max];
intmain()
{
intn,i,hight,low,mid,len,k=0;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
{
printf("Case%d:\nMyking,atmost0roadcanbebuilt.\n\n",++k);
continue;
}
for(i=0;i<n;i++)
{
scanf("%d%d",&hight,&low);
road[hight]=low;//有点类似哈希的做法,这里可以省掉排序
}
dp[1]=road[1];
len=1;
for(i=2;i<=n;i++)
{
low=0;
hight=len;
while(low<=hight)
{
mid=(low+hight)/2;
if(road[i]>dp[mid])
low=mid+1;
else
hight=mid-1;
}
dp[low]=road[i];
if(low>len)
len++;
}
++k;
if(len>1)
printf("Case%d:\nMyking,atmost%droadscanbebuilt.\n\n",k,len);
else
printf("Case%d:\nMyking,atmost%droadcanbebuilt.\n\n",k,len);
}
return0;
}
优质内容筛选与推荐>>
1、斐波拉契数列求兔子的个数2、define与typedef 区别3、【原】PHPExcel导出Excel4、干货分享：vue2.0做移动端开发用到的相关插件和经验总结5、python爬虫从入门到放弃（一）之初识爬虫
长按二维码向我转账
![]()
受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。