5

您需要完成编号为 1..N 的 N 个问题。你已经按照难度递增的顺序排列了问题，第 i 个问题估计了难度级别 i。您还为每个问题分配了等级 vi。具有相似 vi 值的问题本质上是相似的。每天，您将选择问题的一个子集并解决它们。您已经决定，当天解决的每个后续问题都应该比您当天解决的前一个问题更难。此外，为了不让它变得无聊，你解决的连续问题应该在他们的 vi 等级上至少相差 K。你可以解决所有问题的最少天数是多少？

输入：第一行包含测试用例 T 的数量。接下来是 T 测试用例。每个案例的第一行包含一个整数 N 和 K，第二行包含整数 v1,...,vn。

输出：输出 T 行，每个测试用例一个，包含可以解决所有问题的最少天数。

约束：
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

样本输入：
2
3 2
5 4 7
5 1
5 3 4 5 6

样本输出：
2
1

这是来自 interviewstreet 的挑战之一。
下面是我的方法
从第一个问题开始，找出可以解决的最大问题数量，并从问题列表中删除这些问题。现在再次从剩余列表的第一个元素开始，直到现在问题列表的大小为 0 .我从这种方法中得到了错误的答案，所以寻找一些算法来解决这个挑战。

4

4 回答 4

17

按以下方式构造问题的DAG。设p i和p j是两个不同的问题。然后我们将画一条从p i到p j的有向边当且仅当p j可以在同一天连续地在p i之后直接求解。 即，必须满足以下条件：

  1. i < j，因为你应该更早地解决不太困难的问题。
  2. | v我- v j | >= K（评级要求）。

现在请注意，选择在某一天解决的每个问题子集都对应于该 DAG 中的有向路径。你选择你的第一个问题，然后你一步一步地沿着边走，路径中的每一条边对应于同一天连续解决的一对问题。此外，每个问题只能解决一次，因此我们的 DAG 中的任何节点都可能只出现在一个路径中。而且你必须解决所有问题，所以这些路径应该涵盖所有 DAG。

现在我们有以下问题：给定一个有n 个节点的 DAG，找到完全覆盖这个 DAG 的最小数量的非交叉有向路径。这是一个众所周知的问题，称为路径覆盖。一般来说，它是NP难的。然而，我们的有向图是无环的，对于无环图，它可以通过减少匹配问题在多项式时间内求解。反过来，最大匹配问题可以使用Hopcroft-Karp 算法来解决，例如。确切的归约方法很简单，可以在 Wikipedia 上阅读。对于原始 DAG 的每个有向边(u, v)，应添加一条无向边(a u ,b v )到二分图，其中{a i }和{b i }是大小为n的两个部分。

生成的二分图每个部分的节点数等于原始 DAG 中的节点数n。我们知道 Hopcroft-Karp 算法在最坏情况下的运行时间为O(n 2.5 )，300 2.5 ≈ 1 558 845。对于 100 次测试，该算法总共需要不到 1 秒的时间。

于 2012-04-24T18:53:56.817 回答
2

算法很简单。首先，按 对问题进行排序v_i，然后对于每个问题，找出区间 中的问题数(v_i-K, v_i]。这些数字中的最大值就是结果。第二阶段可以完成O(n)，所以成本最高的操作是排序，做整个算法O(n log n)。在此处查看算法对您的数据和电子表格中 K=35 的工作的演示。

为什么这行得通

让我们将问题重新表述为图形着色问题。我们按如下方式创建图 G：顶点将是问题，两个问题之间将有一条边 iff |v_i - v_j| < K。

在这样的图中，独立的集合完全对应于同一天可以解决的问题集合。(<=) 如果集合可以在一天内完成，那么它肯定是一个独立集合。(=>) 如果集合中不包含两个不满足 K 差准则的问题，您可以按照难度对它们进行排序，然后按此顺序解决它们。通过这种方式，这两个条件都将得到满足。

因此，很容易得出，图 G 的颜色与问题在不同日期的时间表完全对应，每种颜色对应一天。

所以，我们要找出图 G 的色度。一旦我们认识到该图是一个区间图，这将很容易，它是一个完美的图，色度等于 cliqueness，两者都可以通过简单的算法找到。

区间图是实线上的区间图，边是相交的区间之间。很容易看出，我们的图是一个区间图（对于每个问题，分配一个区间(v_i-K, v_i]。很容易看出，这个区间图的边正是我们图的边）。

引理1：在区间图中，存在一个顶点，其邻居形成一个团。

证明很容易。您只需采用最低上限（或最高下限）的区间。任何与它相交的区间都有更高的上限，因此，第一个区间的上限包含在所有区间的交集中。因此，它们相互交叉并形成一个派系。qed

引理 2：在一系列封闭于诱导子图并具有引理 1 的属性（顶点的存在，其邻居形成一个集团）中，以下算法产生最小着色：

  1. 找到顶点x，其邻居形成一个集团。
  2. 从图中删除x，使其子图 G'。
  3. 颜色 G' 递归
  4. 用在其邻居上找不到的最少颜色为x着色

证明：在（3）中，算法通过归纳假设+我们的家庭在诱导子图上的接近度来产生子图G'的最佳着色。在 (4) 中，算法仅在x的邻居上n存在大小集团时才选择新颜色。这意味着，对于x，G 中有一个大小团，因此它的色度必须至少为。因此，算法给顶点的颜色总是，这意味着着色是最优的。（显然，该算法会产生有效的着色）。qedn-1nn<= chromaticity(G)

推论：区间图是完美的（完美 <=> 色度 == 派系）

所以我们只需要找到 G 的派系。这对于区间图很容易：您只需处理不包含区间边界的实线段并计算在那里相交的区间数，这在您的情况下更容易，其中间隔有统一的长度。这导致了本文开头概述的算法。

于 2012-05-09T00:05:46.583 回答
0

我们真的需要去路径覆盖吗？我们不能只遵循与LIS类似的策略吗？

输入按复杂度递增的顺序排列。我们只需要为每天要执行的任务维护一堆队列。通过比较所有队列的最后一个元素，将输入中的每个元素分配给一天。无论我们在哪里发现“k”的差异，我们都会将任务附加到该列表中。

例如：5 3 4 5 6

1）输入 - > 5（空列表，所以开始一个新的）

5

2) 3 (只有列表 5 & abs(5-3) 是 2 (k) 所以附加 3)

5--> 3

3) 4（仅列出最后一个 vi、3 和 abs(3-4) < k，所以开始一个新列表）

5--> 3

4

4) 再次 5 (abs(3-5)=k append)

5-->3-->5

4

5) 6 再次 (abs(5-6) < k 但 abs(4-6) = k) 追加到第二个列表)

5-->3-->5

4-->6

我们只需要维护一个包含每个列表的最后一个元素的数组。由于天的顺序（何时完成任务并不重要）我们可以维护最后任务的排序列表，因此，搜索插入新任务的位置只是寻找可以完成的值 abs(vi-k)通过二分查找。

复杂：

循环针对 N 个元素运行。在最坏的情况下，我们最终可能会使用二进制搜索 (log i) 来查询许多 input[i] 的 ceil 值。

因此，T(n) < O( log N! ) = O(N log N)。分析以确保上限和下限也是 O( N log N )。复杂度是 THETA (N log N)。

于 2012-11-22T13:56:20.847 回答
0

所需的最少天数将与 G (DAG) 的互补（无向）图中最长路径的长度相同。这可以使用 Dilworth 定理来解决。

于 2015-12-01T18:05:17.100 回答