Description
一条河,南北岸各有 $n$ 座城市,每座城市有一个坐标。北岸的每座城市在南岸有一个“友好城市”,且不同城市的友好城市不同。如果在每对友好城市之间连边,在这些边互不相交的情况下使边数最多。
数据范围:$n<=2e5, x_i<=1e6$
Solution
$O(n^2)$ 的做法:先把南岸或者北岸排序,然后找另一边的最长不下降子序列。但是过不了这题。
$O(nlog_{n})$ 的做法:优化找最长不下降子序列的过程,使用 $upper$ _ $bound$ 函数找到第一个比当前大的数,替换它。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 300005; struct { int s, n; } a[N]; int n, len = 0, d[N]; bool cmp(city a, city b) { return a.n < b.n; } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].s, &a[i].n); sort(a + 1, a + n + 1, cmp); d[++len] = a[1].s; for(int i = 2; i <= n; i++) { int id = upper_bound(d + 1, d + len + 1, a[i].s) - d; d[id] = a[i].s; if(id > len) len++; } printf("%d", len); return 0; }
|
近期评论