Array

[编程题]Array

热度指数：1064 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

小红有两个长度为n的排列A和B。每个排列由[1,n]数组成，且里面的数字都是不同的。

现在要找到一个新的序列C，要求这个新序列中任意两个位置(i,j)满足:

如果在A数组中C[i]这个数在C[j]的后面，那么在B数组中需要C[i]这个数在C[j]的前面。

请问C序列的长度最长为多少呢？

输入描述:

第一行一个整数，表示N。

第二行N个整数，表示A序列。

第三行N个整数，表示B序列。

满足:N<=50000

输出描述:

输出最大的长度

示例1

输入

5
1 2 4 3 5
5 2 3 4 1

输出

说明

最长的C为1,3,4,5

算法知识视频讲解

Python

lonnya

import bisect

n = int(input())
a = input().split()
b = input().split()
nums = []
#用哈希表速度快
dic = {key: i for i, key in enumerate(a)}
for i in range(n):
    b[i] = dic[b[i]]

#二分查找：这里根据题意应该找降序子列，但是为了直接用库函数，将b反转，这样就找升序子列了
b.reverse()
#贪心加二分查找，比动态规划时间和空间上都更优
d = []
for num in b:
    if not d&nbs***bsp;num > d[-1]:
        d.append(num)
    else:
        ind = bisect.bisect(d, num)
        d[ind] = num
print(len(d))

这样应该最优了

发表于 2025-10-12 22:40:34 回复(0)

Python