俄国沙皇问题

问题

给定一个 N*2 的二维数组,看作是一个个二元组,例如[[a1,b1],[a2,b2],[a3,b3]], 规定:一个如果想把二元组甲放在二元组乙上,甲中的 a 值必须大于乙中的 a 值,甲中的 b值必须大于乙中的 b 值。如果在二维数组中随意选择二元组,请问二元组最多可以往上摞几个?
例如:[[5,4],[6,4],[6,7],[2,3]], 最大数量可以摞 3 个,[2,3] => [5,4] => [6,7] 要求:实现时间复杂度 O(N*logN)的解法

思路

在解决这道题目之前，首先搞清楚一个问题：最长递增子序列 ；最长递增子序列为本题的算法原型。

那么问题来了，最长递增子序列是对一元数列的求解。此问题是二元组。如何将二元转换到一元，将复杂问题转换到我们已知的算法原型上来，成为本题的破题点。这也是俄国沙皇问题最精彩的地方。

重要思想：控制变量
1.以a的值进行升序排列
2.当a有序后，由b的值组成一元序列，对该序列查找最长子序列

现在思考：当a相同时，b该如何排序；这是讲二元转换成一元问题的关键。我们采取的策略是，a值相同时，b降序排列，a按照从小到大排序，b按照从大到小排序。这样保证了，排在后面的二元组。只要b值比前面的二元组大，则一定可以摞上去。a值相同，若b值升序排列，b值大的不一定能摞上。因为只有保证a，b同时大于前面的二元组，才符合题意。

核心代码

struct dot
{
    int a;
    int b;
}dots[length];

int cmp( const void *a , const void *b )
{
    struct dot *c = (dot *)a;
    struct dot *d = (dot *)b;
    if(c->a != d->a)
        return c->a - d->a;
    else
        return d->b - c->b;
}

int searchInsert(int A[], int n, int target) 
{
    int low = 0, high = n-1;
    while(low < high)
    {
        int mid = low+((high-low)>>1);
        if(A[mid] >= target)
            high = mid;
        else
            low = mid+1;
    }
    return low;
}

int LIS_len()
{
    int index = 0;
    int insert = 0;
    //二元组排序，利用cmp规定排序策略
    qsort(dots, length, sizeof(dots[0]),cmp);
    for (int i = 1; i < length; i++)
    {
        if (dots[i].b > h[index])
        {
            index++;
            h[index] = dots[i].b;
        }
        else
        {
            insert = searchInsert(h, index + 1, dots[i].b);
            h[insert] = dots[i].b;
            printf("%d,%d\n", insert, h[insert]);
        }
    }
    return index + 1;
}