arc*_*hit 5 algorithm graph-algorithm
编号为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
这是访谈街的挑战之一.
下面是我的方法
从第一个问题开始,找出最大可能的问题数量可以解决并从问题列表中删除这些问题.现在再次从剩余列表的第一个元素开始并执行此操作直到现在问题列表的大小为0我从这种方法得到错误的答案,所以寻找一些算法来解决这个挑战.
Ski*_*nok 16
以下列方式构建问题DAG.设p i和p j是两个不同的问题.然后我们将绘制从p i到p j的有向边,当且仅当p j可以在 p i之后直接在同一天连续求解.即,必须满足以下条件:
现在请注意,选择在某一天解决的每个问题子集都对应于该DAG中的有向路径.您选择第一个问题,然后逐步跟踪边缘,路径中的每个边对应于在同一天连续求解的一对问题.此外,每个问题只能解决一次,因此我们的DAG中的任何节点可能只出现在一个路径中.而且您必须解决所有问题,因此这些路径应涵盖所有DAG.
现在我们遇到以下问题:给定n个节点的DAG ,找到完全覆盖此DAG的最小数量的非交叉有向路径.这是一个众所周知的问题,叫做Path cover.一般来说,它是NP难的.然而,我们的有向图是非循环的,对于非循环图,它可以使用简化为匹配问题在多项式时间内求解.反过来,最大匹配问题可以使用Hopcroft-Karp算法来解决.确切的简化方法很简单,可以在维基百科上阅读.对于原始DAG的每个有向边(u,v),应该向二分图添加无向边(a u,b v),其中{a i }和{b i }是n的两个部分.
得到的二分图的每个部分中的节点数等于原始DAG中的节点数n.我们知道,霍普克洛夫特-卡普算法运行在为O(n 2.5),在最坏的情况下,和300 2.5 ≈1 558 845 100个对于测试这种算法应该采取下一个总额1秒.