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

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 = 5010n = 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 = 0for 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)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。