所需的天数最少，解决问题列表 [英] Minimum number of days required to solve a list of questions

问题描述

有编号1..1 N麻烦，你需要完成。你已经在安排难度加大的顺序问题，和第i个问题，估计难度我。您还分配了一个等级六每个问题。类似的VI值的问题在本质上是相似。在每一天，你会选择的问题的一个子集，并解决这些问题。你已经决定，每个后续问题解决之日应该比你在这一天解决了previous问题强硬。此外，为了不让它无聊的，连续的问题，你解决应该会有不同的VI等级至少K.什么是最少的天数中，你可以解决所有的问题？

There are N problems numbered 1..N which you need to complete. You've arranged the problems in increasing difficulty order, and the ith problem has estimated difficulty level i. You have also assigned a rating vi to each problem. Problems with similar vi values are similar in nature. On each day, you will choose a subset of the problems and solve them. You've decided that each subsequent problem solved on the day should be tougher than the previous problem you solved on that day. Also, to not make it boring, consecutive problems you solve should differ in their vi rating by at least K. What is the least number of days in which you can solve all problems?

输入： 第一行包含测试用例T. T检验的情况下遵循的数量。每一种情况下包含一个正整数N和K在第一行上，其次是整数V1，...，Vn的在第二行

Input: The first line contains the number of test cases T. T test cases follow. Each case contains an integer N and K on the first line, followed by integers v1,...,vn on the second line.

输出： 输出T线，一个用于每个测试的情况下，含天中，所有问题都可以解决的最小数

Output: Output T lines, one for each test case, containing the minimum number of days in which all problems can be solved.

约束：
1＆LT; = T＆LT; = 100
1＆LT; = N＆LT; = 300
1＆LT; = VI＆LT; = 1000
1＆LT; = K＆LT; = 1000

Constraints:
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

Sample Input:
2
3 2
5 4 7
5 1
5 3 4 5 6

示例输出：
2
1

Sample Output:
2
1

这是从interviewstreet的挑战之一。
下面是我的方法
开始从第一个问题，并找出最大可能的一些问题可以解决并删除问题这些问题list.Now再次从电量及名单的第一个元素开始，但是这个到现在的问题列表的大小为0。 我得到错误的答案，从这个方法，以便寻找一些算法中解决了这一难题。

This is one of the challenge from interviewstreet.
Below is my approach
Start from 1st question and find out max possible number of question can be solve and remove these questions from the question list.Now again start from first element of the remainning list and do this till now size of the question list is 0. I am getting wrong answer from this method so looking for some algo to solve this challenge.

推荐答案

构造一个 DAG 的问题以下列方式。让我们的 P <子>我 和 P <子>Ĵ 的是两个不同的问题。然后，我们将以此为导向边缘从 P <子>我 的到 P <子>Ĵ 的当且仅当 P <子>Ĵ 的是可以解决的直接 P <子后>我 的在同一天，连续。即，在下列条件必须满足：

Construct a DAG of problems in the following way. Let p_i and p_j be two different problems. Then we will draw a directed edge from p_i to p_j if and only if p_j can be solved directly after p_i on the same day, consecutively. Namely, the following conditions have to be satisfied:

1. 的 I＆LT; Ĵ的，因为你要解决的难度较低的问题前面。
2. | v <子>我 的 - 的 v <子>Ĵ的 | > = K（评级要求）。

1. i < j, because you should solve the less difficult problem earlier.
2. |v_i - v_j| >= K (the rating requirement).

现在注意到的是选择在某一天需要解决的问题每个子集对应于在DAG中的向路径。你选择你的第一个问题，然后你按照边一步一步来，在路径上的每个边对应于对问题已经解决了连续在同一天。此外，每个问题是可以解决的一次，所以在我们的DAG任何节点可以只出现在正好一个路径。而且你必须解决所有的问题，所以这些路径应涵盖所有的DAG。

Now notice that each subset of problems that is chosen to be solved on some day corresponds to the directed path in that DAG. You choose your first problem, and then you follow the edges step by step, each edge in the path corresponds to the pair of problems that have been solved consecutively on the same day. Also, each problem can be solved only once, so any node in our DAG may appear only in exactly one path. And you have to solve all the problems, so these paths should cover all the DAG.

现在，我们有以下的问题：给定一个DAG的 N 的节点，发现不相交的最小数量指示，完全覆盖这个DAG路径。这是一个众所周知的问题称为路径覆盖。一般来说，它是一个NP难。然而，我们的向图是无环的，而对于无环图可在多项式时间内使用减少到<一个解决href="http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs"相对=nofollow>匹配问题。最大匹配问题，反过来，可以使用 Hopcroft - 卡普算法解决，例如。确切的还原方法是容易的，可以读，说，<一href="https://en.wikipedia.org/wiki/Maximum_flow_problem#Minimum_path_cover_in_directed_acyclic_graph"在维基百科相对=nofollow>。对于每一个有向边的（U，V）的原始DAG一个的应该添加一个无向边缘的（A <子> U 的 B <子> v ）的对偶图，其中的 {A <子>我} 和 {B <子>我} 的是大小两部分组成的 N 的。

Now we have the following problem: given a DAG of n nodes, find the minimal number of non-crossing directed paths that cover this DAG completely. This is a well-known problem called Path cover. Generally speaking, it is NP-hard. However, our directed graph is acyclic, and for acyclic graphs it can be solved in polynomial time using reduction to the matching problem. Maximal matching problem, in its turn, can be solved using Hopcroft-Karp algorithm, for example. The exact reduction method is easy and can be read, say, on Wikipedia. For each directed edge (u, v) of the original DAG one should add an undirected edge (a_u, b_v) to the bipartite graph, where {a_i} and {b_i} are two parts of size n.

在所得二分图的各部分的节点的数量等于节点在原始的DAG的 N 的数量。我们知道，Hopcroft-卡普算法运行在的为O（n ^2.5 ）的在最坏的情况下，和300 ^2.5 ≈1 558 845 100对于测试这个算法应该在1秒的总和。

The number of nodes in each part of the resulting bipartite graph is equal to the number of nodes in the original DAG, n. We know that Hopcroft-Karp algorithm runs in O(n^2.5) in the worst case, and 300^2.5 ≈ 1 558 845. For 100 tests this algorithm should take under a 1 second in total.

这篇关于所需的天数最少，解决问题列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！