[C++] 共建友好城市

共计 857 个字符，预计需要花费 3 分钟才能阅读完成。

有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的 n 个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航道不相交的情况下，被批准的申请尽量多。

输入描述

第 1 行，一个整数 n，表示城市数。

第 2 行到第 n+1 行，每行两个整数，中间用一个空格隔开，分别表示南岸和北岸的一对友好城市的坐标。

输出描述

仅一行，输出一个整数，表示政府所能批准的最多申请数。

样例

输入：

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出：

4

数据范围

1 \le n \le 2 \times 10^5, 0 \le x_i \le 10^6

答案

#pragma GCC optimize(3)
#include <iostream>
#include <algorithm>

using namespace std;

struct cityBind{
    int north;
    int south;
};

int main(){ios::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    cityBind *a = new cityBind[n];
    for(int i=0;i<n;i++) cin >> a[i].north >> a[i].south;

    sort(a, a+n, [](cityBind x, cityBind y){return x.north < y.north;});

    int *b = new int[n], ans = 0;
    for(int i=0;i<n;i++){int j = upper_bound(b, b+ans+1, a[i].south) - b;
        b[j] = a[i].south;
        ans = max(ans, j);
    }
    cout << ans;
    return 0;
}

解释

本题实质上就是求最长上升子序列长度，利用标准库函数可以非常快的完成。

先将友好城市按其中一岸排序，然后动规 + 二分查找右边界即可。