清洗所有污点所需的最少时间

Question

考虑从0到正方向的x轴上的直线上的点.

有N个人站在一些点上，而M点是肮脏的

我需要找出清理所有污点所需的最短时间。

每一秒，每个人都可以向左或向右移动，也可以停留。

当一个人说到一个污点时，重点就会被清理干净。

示例：

假设人在5,10，脏=8，人在第5和第10点，第8点。

就是肮脏的地方。第二个人可以走到第8点，把它擦干净。这需要2秒

假设100,300和脏= 200,400，第一个人可以从100点到另一点

200同时，第二个人可以从300点到400点

这需要100秒钟。

不知道怎么接近它。一个人是否能跟随贪婪的方法，简单地走向

最接近的点。但是如果有两个点是最近的

Answer 1

一般性发言

首先，我们将尝试通过引入一些语句来限制搜索空间，让自己相信这些都是真的。

，

• ，两个人相遇或擦肩而过是没有意义的。->每个点将由最靠近左或右的人清理，最多由2^M情况下的->来检查
• ，在最优路径上的人最多会改变方向一次。根据需要清理的点，一个人花费的时间可以定义为：->

val s = start position
val l = min(points to clean)
val r = max(points to clean)
val dl = s - l
val dr = r - s
val time = when {
 dl <= 0 -> dr //points only to the right
 dr <= 0 -> dl //points only to the left
 else -> min(dl, dr) * 2 + max(dl, dr) //points on both sides, take shorter side twice
}

蛮力算法

val cases: List<Map<Person, List<Point>> = enumerate all 2^M cases where each point is either assigned to the closest person to the left or closest person to the right
val minTime = cases.minOf { case -> case.entries.maxOf { (person, points) -> time(person, points) } }

该算法的时间复杂度主要是通过枚举O(2^M)中的实例来决定的。

最优的方法是首先找到所有的左右侧人。