本题求最大上升子序列，这个很容易看出来。数据大小是50万，所以不能用O(n^2)的方法来求。因为1000万以上次循环就可能超时。

若用二分来解决，时间复杂度为O(nlogn)。

代码使用了我认为的最经典的二分形式。

 

#include 
     
      using namespace std;const int MAXCITYNUM = 500005;int poorCity[MAXCITYNUM],ans[MAXCITYNUM];int main (){
    int caseNum = 1,cityNum;    while (scanf("%d",&cityNum) != -1)    {        int richCity;        for (int i = 1;i <= cityNum;i ++)/* 没说数据按rich city的编号由小到大给出 */        {            scanf("%d",&richCity);            scanf("%d",&poorCity[richCity]);        }        ans[1] = poorCity[1];        int low,high,mid,len = 1;        for (int i = 2;i <= cityNum;i ++)        {            low = 1 , high = len;            while (low <= high)            {                mid = (low + high) / 2;                if (ans[mid] >= poorCity[i])                    high = mid - 1;                else                    low = mid + 1;            }            ans[low] = poorCity[i];            if (low == (len + 1))                len ++;        }        printf("Case %d:\n",caseNum);        caseNum ++;        if (len == 1)/* 注意细节 */            printf("My king, at most %d road can be built.\n",len);        else            printf("My king, at most %d roads can be built.\n",len);        printf("\n");    }    return 0;}