洛谷 P2782 友好城市 题解

发表于 | 分类于 | | 热度: ℃

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300005;
struct city
{
    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;
}