以下问题的O(N*LogN)算法

Question

以下问题的O(N*LogN)算法

10

有如下问题：

某城市中最负盛名的运动俱乐部正好有N名会员。每个会员都强壮美丽。更确切地说，该俱乐部的第i个成员（按其入会时间编号）具有力量Si和美丽Bi。由于这是非常负盛名的俱乐部，其成员非常富有而且是不同凡响的人物，所以他们经常出现极端的仇恨。严格来说，如果S _{i ≤ S_j且B _i ≥ B _{j或S_i ≥ S_j且B_i ≤ B_j，那么俱乐部的第i个成员X先生就讨厌俱乐部的第j个成员Y先生（如果X先生的两种属性都大于Y先生的相应属性，他甚至不会注意到他，另一方面，如果他的两种属性都较小，则他非常尊重Y先生）。}}

为了庆祝2003年新年，该俱乐部的管理层计划组织一个派对。但是，他们担心如果同时邀请两个互相憎恨的人参加派对，在喝上一两杯后，他们会开始打架。因此，不应邀请互相憎恨的两个人。另一方面，为了保持俱乐部的声望在适当水平，管理层希望邀请尽可能多的人。

作为管理层中唯一不怕接触计算机的人，你需要编写一个程序来确定应该邀请哪些人参加派对。

输入

*输入文件的第一行包含整数N-俱乐部成员的数量（2≤N≤100,000）。下一行包含每个成员的两个数字-S_i和B_i（1≤S_i，B_i ≤10⁹）。

输出

在输出文件的第一行上打印可以邀请参加聚会的最大人数。在第二行输出N个整数-要邀请的成员号码按任意顺序。如果存在多个解决方案，则输出任何一个。

示例测试

输入

输出

  2
  1 4

我试图解决一个问题，但是我的算法复杂度为O(N^2)，而且由于2<=N<=100000，需要改进算法。我正在使用最长递增子序列动态规划算法来解决这个问题，它的时间复杂度是O(N^2)。有没有人有什么想法来改进算法？

- Timofey

1

我猜这是作业，如果不是，请再次删除标签。 - Björn Pollex

TL;DR。好的...其实不是这样的。但你应该将其翻译成一个数学/编程问题。除此之外：你是否在寻找关系（X钦佩Y）中的最大链？......（Dilworth） - tgmath

2

@Space_C0wb0y：这不是一道作业题，而是来自ACM竞赛的问题。如果你能在1小时内解决它，那么你可以把自己视为一个优秀的程序员 ;) - Timofey

@tgmath: 没错，需要在关系（X钦佩Y）中找到最大链，问题是N<=10^5，普通算法的复杂度为O(N^2)，这在2秒内无法实现。 - Timofey

你可以尝试假设随机变量是均匀分布的。这将使您可以假设最大团是（S，B）图上主对角线的近似，并因此为您提供一种快速的方法来丢弃大多数点，以便您只需要处理O（n ** 0.5）个点。这是一个技巧，但是是合理的。 - Donal Fellows

1

尊重关系定义了一个偏序。您正在尝试找到与此偏序相关的最长可能链a < b < c。 - hugomg

5个回答

2

这里提供一个 O(n log(n)) 的解法。

首先按美丽值升序、力量值降序对人进行排序，消除重复项（可以在此处显式消除，也可以在下一步隐式跳过它们）。

遍历列表。在遍历时，维护一个平衡树，其中存储可能成为最大升序链中下一个人的人。每个人应该与当前链的长度和指向其余链表中其他人的指针一起存储。该树应按强度排序。

更具体地说，当您看到一个新人时，请找到树中下一个最弱的人（没有人是OK的），并构造三元组(person, length of chain, pointer to chain)。将该人插入树中。如果树中下一个更强的人的链不比当前人长，则删除该人。所有这些操作都是O(log(n))。

当您处理完所有人时，树中的最大记录将有一个人位于人的最大链的末端，链的长度以及指向链中其余人的链接列表的指针。那就是你的答案，请打印出来。

为了展示您的样本数据，这里是您需要开始的内容：

这代表着：

{person: 1, beauty: 1, strength: 1}
{person: 2, beauty: 2, strength: 1}
{person: 3, beauty: 1, strength: 2}
{person: 4, beauty: 2, strength: 2}

按美丽程度递增，然后按强度递减排序（没有重复项），得到：

{person: 3, beauty: 1, strength: 2}
{person: 1, beauty: 1, strength: 1}
{person: 4, beauty: 2, strength: 2}
{person: 2, beauty: 2, strength: 1}

为了简化事情，我将只用一个排序集合来表示树。这并不是它在内存中应该被表示的方式。

插入第三个人后：

{person: 3, strength: 2, length: 1, next_person: null}

下一个人1撞到人3。

{person: 1, strength: 1, length: 1, next_person: null}

然后人4在人1之后。（我已将链接列表编写为嵌套数据结构，在实际中应该是一个链接列表。）

{person: 1, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

然后第二个人撞了第一个人。

{person: 2, strength: 1, length: 1, next_person: null}
{person: 4, strength: 2, length: 2, next_person: {person: 1, next_person: null}}

要找到你的答案，请查看树的末尾，第4个人指向第1个人。你的答案是长度为2，然后（从最好到最差）是第4个人然后是第1个人。

- btilly

更改您的示例输入，使人们的力量和美丽不同。（例如，人1实际上应该讨厌人3） - hugomg

此外，如果您将示例更改为 less verbose（仅将人表示为元组，并且不要递归整个链接列表 - 如果我没有错的话，它应该始终指向树上可见的人），可能会有所帮助。 - hugomg

@missingno：你错了，之前的人可能是被一个力量较低、美貌较高的人撞下树的。这在第二个人撞到第一个人后发生了。至于这个例子，我使用了问题陈述中的例子。另外，你说得对，第一个人应该讨厌第三个人。嗯，我的例子有点错。我马上会修正。 - btilly

1

如果你将俱乐部成员视为顶点，将“喜欢”视为边（即如果两个成员彼此不讨厌，则相应的顶点之间存在一条边），则可以将问题重新表述如下：

找到最大的顶点子集，使得子集中所有顶点之间都存在边。

事实上，一个所有顶点之间都有互相边的子集被称为团或完全子图。

如果不能利用图的其他特征，找到最大团需要指数时间（请参见此链接）。本文介绍了Bron-Kerbosch算法。

在（S，B）平面上绘制成员，可以看到“like”边对应于从顶点向12点至3点和6点至9点之间的方向延伸的线。很容易构造一个这样的边相交的示例，因此它不是一个平面图。

不幸的是，“like”关系不是传递性的，即如果A喜欢B，B喜欢C，这并不意味着A也喜欢C（同样，在（S，B）平面上很容易看出）。

- Andre Holzner

不幸的是，“喜欢”的关系不是传递性的，如果它是传递性的，则有可能在O（N * logN）时间内解决问题。（http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms） - Timofey

喜欢不是可传递的，但“尊重”是。 - hugomg

0

以下是一些关于btilly的解决方案如何工作的论点：

实际上，respect和ignore在对称意义上是相等的，如果A尊重B，则B忽略A，因此只需要考虑其中一个关系，例如respect。
正如missingno所指出的那样，respect关系是可传递的，这意味着如果A尊重B且B尊重C，则A也尊重C（以及B尊重的所有人）。
考虑以下图形：顶点表示成员，从A到B的有向边表示A尊重B（或等效地，B忽略A）。消除重复项后（可以将其视为具有相应多重性的成员权重），我们意识到不能有循环（如果A尊重B，则不可能通过其他成员B尊重A，在某个时候必须有一条朝错误方向的边），即我们有一个有向无环图。
考虑通过图形的路径：如果成员A在该路径上，路径上的所有其他顶点都被A尊重（进一步“下游”）或被A忽略（进一步“上游”）。因此，通过图形的任何路径表示彼此喜欢的成员组。
另一方面，如果A和B之间没有路径，他们互相憎恨（否则它们之间将有例如直接边）。
因此，我们已经将问题重新表述为找到有向无环图中的最长路径 （其中每条边的权重为1），一旦构建了这样的图，就可以在线性时间内完成。

问题在于构建图形的速度比O(N^2)更快，即不必遍历所有可能的顶点对。

这是btilly的示例图形（箭头表示“尊重”）：

example graph

当到达顶点A时，我们只需要添加“最近”的邻居，也就是不像D那样可以通过其他顶点（如B和C）到达的邻居。
这就是为什么要按一个坐标升序排列，另一个坐标降序排列的原因：在我们添加了从A到B的边之后，我们不会再添加从A到D的直接边（因为通过B或C到达D更好），所以我们只需要查看位于B右侧和下方的顶点（那些不能与B相连的顶点）。

- Andre Holzner

-1

两个力量和美貌都相同的人互相憎恨，而且力量和美貌的限制非常紧密...

- adlskf

恶意投票。很好。如果你能让N足够小，O(N^2)也没问题。 - adlskf

我明白了，原来是10的9次方。既然只有Tim知道，我想我不会再发布n log n的解决方案了。 - adlskf

请提供有建设性的答案！:( - NirmalGeo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

我认为你的 O(n^2) 解决方案甚至都不正确，更不用说高效了。如果你有像这样的内容：

答案是3。然而，经典的LIS算法会给出2。你有考虑到这一点吗？

你可以按S_i排序，并在B_i上应用LIS算法，在O(n log n)时间内完成。你可以使用段树或涉及二进制搜索的更简单的算法。如果需要更多帮助，请告诉我。

总复杂度为O(n log n)：排序和LIS都可以在这个时间内完成。