这题n^2 算法超时
#include<stdio.h> #define N 500001 int a[N],b[N]; int main () { //freopen("1025.txt","r",stdin); int i,n,x,y,c=1,len,low,high,mid; while(scanf("%d",&n)!=EOF) { for (i=0;i<n;i++) { scanf("%d%d",&x,&y); a[x-1]=y; b[i]=1; } len=1; b[0]=a[0]; for (i=1;i<n;i++) { low=0; high=len-1; while(low<=high) { mid=(low+high)>>1; if (b[mid]<a[i]) low=mid+1; else high=mid-1; } b[low]=a[i];//b[] 不是LIS 是长度为i的LIS的最小末尾 if (low>len-1) len++; } printf("Case %d:/n",c++); if (len==1) printf("My king, at most %d road can be built./n/n",len); else printf("My king, at most %d roads can be built./n/n",len); } }
