我正在从算法和数据结构(我在一个月内完成)中学习考试,但我无法为这个问题找到有效的算法:
我们在这条线上得到 1 <= n <= 5000 个点。每个点具有不同的自然坐标 0 <= d <= 10^6 和(不一定不同)自然点时间0 <= t <= 10^9 以秒为单位。我们可以从任意点开始,每秒将当前坐标更改 +/-1。问题是以这样的顺序访问所有点,即在经过他的点时间之前访问每个点。找出这次旅行的最短总时间(以秒为单位),或者说这是不可能的。
例如,给出 5 个点(坐标,点时间):
(1,3), (3,1), (5,6), (8,19), (10,15),有可能,当我们旅行时访问坐标:3 -> 1 -> 5 -> 8 -> 10,我们得到最小总时间,等于:11。
我的第一个想法是按字典顺序对所有点进行排序:(点时间,坐标),然后按此顺序访问它们。当然,当第i个点和第(i+1)个点之间有点时,我们可以在访问第(i+1)个点之前访问它们。但不幸的是,没有论据为什么这种贪婪的方法应该奏效,尽管它很难实施。也许我试图解决它太快?n 很小,所以我想 O(n^2) 应该没问题。
我找到了其他输入示例,认为它可能会帮助我找到解决方案。但现在我只看到我必须找到所有可能的 $n!$ 排列中的一个排列。
输入示例:
点(也分别由坐标,点时间给出):(0,4),(1,2),(4,5):令人惊讶的是(我认为)我们必须访问它们:0 -> 1 -> 4,因为任何不同的顺序都不满足问题文本中最后一句之前的条件。
点数:(0,7), (1,2), (2,1), (3, 4), (4,11),唯一有趣的是:2 -> 1 -> 3 -> 0 -> 4,这需要我们 10 秒。
任何人都可以帮忙吗?