algorithm - 打印最大列表

Question

我们有 N 个水果的集合 F={a1,a2,a3,…,aN}。每个 Fruits 都有价格 Pi 和维生素含量 Vi。现在我们必须以这样一种方式排列这些水果，即列表中包含的价格按升序排列，列表中的维生素含量按降序排列。

例如:N=4

圆周率:2 5 7 10

六:8 11 9 2

这是确切的问题 https://cs.stackexchange.com/questions/1287/find-subsequence-of-maximal-length-simultaneously-satisfying-two-ordering-constr/1289#1289

Answer 1

我会尝试将问题减少到 longest increasing subsequent problem .

1. 根据第一个标准[维生素]对列表进行排序
2. 然后，在修改列表中找到最长的递增后续，根据第二个标准[价格]

这个解决方案是 O(nlogn)，因为步骤 (1) 和 (2) 都可以在 O(nlogn) 中完成。
查看维基百科文章，在 Efficient Algorithms 下- 如何实现最长递增后续

编辑:

如果您的列表允许重复项，您的排序 [步骤 (1)] 将必须按第二个参数作为次要条件进行排序，以防主要条件相等。

示例 [您的示例 2]:

Pi::99 12 34 10 87 19 90 43 13 78
Vi::10 23 4 5 11 10 18 90 100 65

在第 1 步之后，您得到 [当 Vi 是主要条件时降序排序]:

Pi:: 013 43 78 12 90 87 87 99 10 34
Vi:: 100 90 65 23 18 11 10 10 05 04

第二步寻找Pi中最长的递增子序列，得到:

(13,100), (43,90), (78,65), (87,11), (99,10)

作为一个可行的解决方案，因为它是排序列表中的递增子序列 [according to Pi]。

附言在这里我假设你想要的递增子序列是严格递增的，否则结果是 (13,100),(43,90),(78,65),(87,11),(87,10),( 99,10) - 这是一个较长的子序列，但它不是根据 Pi 和 Vi

严格增加/减少的