hdu 1025 Constructing Roads In JGShining's Kingdom(二分法+最長上升子序列)

hdu 1025 Constructing Roads In JGShining's Kingdom(二分法+最長上升子序列)

題目大意：河的兩岸有兩個不同的國家，一邊是窮國，一邊是富國，窮國和富國的村莊的標號是固定的，窮國要變富需要和富國進行交流，需要建橋，並且建的橋不能夠有交叉。問最多可以建多少座橋。

思路：建路時如下圖所示

當一邊的點已經固定了的時候，另外一邊按照從小到大的序列與當前的邊連接，得到最少的交叉。

題目給的第二組測試數據，如果按照圖一則可以建2座橋，圖二建一座橋

3
1 2
2 3
3 1

圖一 圖二

一開始用的是一般的最長上升子序列，結果超時。後來想到之前poj做過的3903 Stock Exchange（二分法），當時也是超時後來用的是二分法做的就過了。又敲了一遍代碼還是沒有過，提示的是超時。看了討論區以後發現輸出格式不對，存在一條以上的路時road為復數roads。以前從來沒有遇到這樣的輸出，這次也算是一次積累吧!改了以後還是超時。上網百度了一下人家的做法，發現了一個新的技巧，因為每一個點只有一個所以不用排序，輸入的u v可以直接用數組標記，line[u] = v;而我之前做的代碼是先用sort函數將u排序後求解，時間變長。嗯，不錯這又是一個好方法。

#include 
#include 
#include 
#include 
using namespace std;
#define  MAX 500005
int point[MAX];
int num, stack[MAX], top;
int main()
{
    int i, cnt, max, a, b;
    int low, high, mid;
    cnt = 0;
    while (scanf("%d", &num)!=EOF)
    {
       cnt++;
       max = 0;
       for (i=0; istack[top])
            {
                top++;
                stack[top] = point[i];
            }
            else
            {
                low = 0;
                high = top;
                while (low <= high)
                {
                       mid = (high+low) / 2;
                    if (point[i] > stack[mid])
                        low = mid + 1;
                    else
                        high = mid - 1;
                }
                stack[low] = point[i];
            }    
        }
        if (top==1)
            printf("Case %d:\nMy king, at most %d road can be built.\n\n", cnt, top);
        else
             printf("Case %d:\nMy king, at most %d roads can be built.\n\n", cnt, top);
    }
    return 0;
}