---
title: "友好城市"
created: 2025-11-28
tags:
  - 算法
---

# 友好城市

## 题目 友好城市

![[image-9b4ccd27.png]]

![[image-5c6f6967.png]]

## 思路分析

初始给定我们 n座打算建造的桥

每座桥有两个参数 x1和 x2，表示该桥一头连接在上岸坐标为x1的地方，一头连在下岸坐标为x2 的地方

找出一种建桥方案，使得在所有建造的桥不相交的前提下，建造尽可能多的桥

![[image-da624de5.png]]

红色虚线表示初始提供的打算建造的桥

我们要找出的方案是在不相交的前提下的最大建桥数量

也就是上面的绿线连接而成的方案

先想一下暴力怎么做

很容易想到，我们可以枚举所有的方案，然后检查方案是否合法，如果合法就考虑是否能够更新最大值答案

这么做的时间复杂度是 $O(2^n)$，而 n的数据范围是 5000，毫无疑问会超时。

所以，我们就需要找出一些性质进行优化

既然是要暴力枚举，我们可以考虑一个枚举方案，按照上岸的坐标从小到大来枚举

然后我们只需关心下岸的坐标之间有何关系即可

于是，可以轻易发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的

具体见下图：

蓝色表示该方案按照上坐标从小到大先选出来的桥

红色表示该方案的下一座桥的下坐标不是从小到大的，绿色表示是从小到大的

![[image-7ff67790.png]]

因此，该方案中，在上坐标排序的情况下，下坐标次序不是从小到大的，则必然不合法（会有相交）

于是，这题就变成了：桥以上坐标从小到大排序后，找出下坐标的最长上升子序列长度

妙……

用pair把桥的两头存下来 然后按第一维（上坐标）排序

然后只需要对排序后的下坐标求最长上升子序列就行了

由于这题是只需要一个最大长度 所以还可以用单调栈加二分进一步优化

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define x first

#define y second

typedef pair<int,int> PII;

const int N=5010;

int f[N];

PII bridge[N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>bridge[i].x>>bridge[i].y;

    sort(bridge+1,bridge+n+1);

    for(int i=1;i<=n;i++){

        f[i]=1;

        for(int j=1;j<i;j++){

            if(bridge[j].y<bridge[i].y)

                f[i]=max(f[i],f[j]+1);

        }

    }

    int res=0;

    for(int i=1;i<=n;i++)

        res=max(res,f[i]);

    cout<<res;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define x first

#define y second

typedef pair<int,int> PII;

const int N=5010;

PII bridge[N];

int stk[N],top;

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>bridge[i].x>>bridge[i].y;

    sort(bridge+1,bridge+n+1);

    for(int i=1;i<=n;i++){

        if(top==0 || bridge[i].y>stk[top])

            stk[++top]=bridge[i].y;

        else{

            *lower_bound(stk+1,stk+top+1,bridge[i].y)=bridge[i].y;

        }

    }

    cout<<top;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最低通行费|最低通行费]] 🏠 [[00-刷题理模型]] ➡️ [[合唱队形|合唱队形]]