1012. 友好城市（LIS+排序）

蓝桥杯国赛指南，详情见​​专栏​​

文章目录

• ​​Question​​
• ​​Ideas​​
• ​​Code​​

Question

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

输入格式
第1行，一个整数N，表示城市数。

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

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

数据范围
1≤N≤5000,
0≤xi≤10000
输入样例：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
输出样例：
4

Ideas

这个题最难的就是怎么想到用排序，进而转换为LIS问题。
一方面，如果任意一岸上的城市有序，那么要满足两岸相连城市无相交，另外一岸能够相连的城市就得满足严格单调递增；
另一方面，如果不满足严格递增，那么两岸城市就无法不相交。
所以能够推出：在一边城市有序（升序）的情况下，另外一岸边必须单调（递增），就可以转换为最长上升子序列模型了。时间复杂度为O(N^2)

Code

# 最长上升子序列模型：求所有直线不相交的的最大数量，需要先对一个维度上进行排序
# O(N^2)
N = 5010
n = int(input())
a = []
for i in range(n):
a.append(list(map(int,input().strip().split())))

f = [0 for i in range(N)]
a.sort(key=lambda x:(x[1],x[0])) # 默认根据a的每一个元素0索引位置排序

res = 0
for i in range(n):
f[i] = 1
for j in range(i):
if a[i][0] > a[j][0]:
f[i] = max(f[i],f[j]+1)
res = max(res,f[i])
print(res)