1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MaxSize 500005
 5 struct trade{
 6     int x,y;
 7 };
 8 trade tp[MaxSize];
 9 int dp[MaxSize];//表示到第i個(gè)點(diǎn)時(shí)的可得到的最長(zhǎng)不降單調(diào)序列
10 int num[MaxSize];//存儲(chǔ)輸入的序列
11 int n,m;
12 int cmp(trade a,trade b){
13     return a.x<b.x;
14 }
15 inline void scan(int &x){
16      char ch;
17      while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
18      while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
19 }
20 int main(){
21     //freopen("in.txt","r",stdin);
22     int i,no=1;
23     while (~scanf("%d",&n)){
24         for(i=0;i<n;i++){//輸入交易
25             scan(tp[i].x);
26             scan(tp[i].y);
27         }
28         //sort(tp,tp+n,cmp);//排序，按第二梯隊(duì)查找最長(zhǎng)不降單調(diào)子序列
29         memset(dp,0,sizeof(dp));
30         dp[0]=tp[0].y;
31         m=0;
32         for(i=1;i<n;i++){//二分的設(shè)計(jì)是難點(diǎn) 但思路其實(shí)很明了 
33             //為減小比較規(guī)模 應(yīng)該利用dp數(shù)組 做每個(gè)可能序列的最大值存儲(chǔ) 這是時(shí)間優(yōu)化關(guān)鍵
34             int mid,low=0,high=m;
35             while (low<=high){
36                 mid=(low+high)>>1;
37                 if(tp[i].y>dp[mid])
38                     low=mid+1;
39                 else
40                     high=mid-1;
41             }
42             dp[low]=tp[i].y;
43             if(low>m)
44                 m=low;
45         }    
46         printf("Case %d:\nMy king, at most %d %s can be built.\n\n",no++,m+1,m?"roads":"road");
47     }
48     return 0;
49 }
50