武汉 网站制作案例/赚钱软件

    题意是说在路两旁分别有富裕的城市和穷困的城市，他们之间打算连接起来，而每个城市间只会有1条路（比如1连到2就不会再出现1连到3，表示一开始忽略了这点......然后考虑了半天这种情况怎么处理才好......），而且这些路之间不能交叉，给出现在想连在一起的城市的计划方案，问最多能连几条路出来。

    看上去很复杂，但其实上，只要按一边城市的顺序排好，再求出另一边的最长子序列就可以了，因为一边排好之后，只要另一边的数字比前面大，那么就一定不会出现交叉，于是，用最长子序列来做......

    下面代码，TLE了......

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct road
{int st;int en;
};int maxlen[500005];
road a[500005];int cmp(road x,road y)
{if(x.st!=y.st)return x.st<y.st;return x.en<y.en;
}int max(int x,int y)
{return x>y?x:y;
}int main()
{int n;int i,j,k=0;int t;int ans;while(scanf("%d",&n)!=EOF){k++;for(i=0;i<n;i++){scanf("%d%d",&a[i].st,&a[i].en);maxlen[i]=1;}sort(a,a+n,cmp);for(i=1;i<n;i++){for(j=0;j<i;j++){if(a[i].en>a[j].en){maxlen[i]=max(maxlen[i],maxlen[j]+1);}}}ans=*max_element(maxlen,maxlen+n);cout<<"Case "<<k<<":"<<endl;if(ans==1)cout<<"My king, at most 1 road can be built."<<endl<<endl;elsecout<<"My king, at most "<<ans<<" roads can be built."<<endl<<endl;}return 0;
}

    好吧，结果就是，超时了= =然而之前有最长子序列的题我都是怎样写的啊......好吧，百度了下发现，原来还有更快的方法，这种方法是O(n^2)，而还有一种O(nlogn)的求最长子序列算法，果然，参考着网上的改正过来后就AC了......

    简单来说这种方法就是记录下来递增子序列的最小末尾，然后不断更新，用下一个数与这些最小末尾再进行比较与插入，而在比较的时候可以采用二分查找的方式，这样复杂度就只需nlogn就可以得出结果了。

    这里贴一个学习时看到的博客地址，里面对这个算法的过程说的很详细，我就不具体的再说了= =：http://blog.csdn.net/shuangde800/article/details/7474903

    然后下面是AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct road
{int st;int en;
};road a[500005];
int b[500005],c[500005];int cmp(road x,road y)
{if(x.st!=y.st)return x.st<y.st;return x.en<y.en;
}int max(int x,int y)
{return x>y?x:y;
}int fin(int *t,int len,int n)
{int left=0,right=len,mid=(left+right)/2;while(left<=right){if(n>t[mid])left=mid+1;else if(n<t[mid])right=mid-1;elsereturn mid;mid=(left+right)/2;}return left;
}int main()
{int n;int i,j,k=0;int t;int len;while(scanf("%d",&n)!=EOF){k++;for(i=0;i<n;i++){scanf("%d%d",&a[i].st,&a[i].en);}sort(a,a+n,cmp);b[0]=1;c[0]=-1;c[1]=a[0].en;len=1;for(i=1;i<n;i++){j=fin(c,len,a[i].en);c[j]=a[i].en;if(j>len)len=j;}cout<<"Case "<<k<<":"<<endl;if(len==1)cout<<"My king, at most 1 road can be built."<<endl<<endl;elsecout<<"My king, at most "<<len<<" roads can be built."<<endl<<endl;}return 0;
}