46 lines
1.3 KiB
Kotlin
46 lines
1.3 KiB
Kotlin
|
class Solution {
|
||
|
|
fun <A, B> product(
|
||
|
|
xs: Sequence<A>,
|
||
|
|
ys: Sequence<B>,
|
||
|
|
): Sequence<Pair<A, B>> = xs.flatMap { x -> ys.map { y -> x to y } }
|
||
|
|
|
||
|
|
fun <A, B> product(
|
||
|
|
xs: Iterable<A>,
|
||
|
|
ys: Iterable<B>,
|
||
|
|
): Sequence<Pair<A, B>> = product(xs.asSequence(), ys.asSequence())
|
||
|
|
|
||
|
|
private fun abs(x: Int): Int = listOf(-x, x).max()
|
||
|
|
|
||
|
|
private data class Factory(val position: Int, var limit: Int)
|
||
|
|
|
||
|
|
fun minimumTotalDistance(
|
||
|
|
robot: List<Int>,
|
||
|
|
factory: Array<IntArray>,
|
||
|
|
): Long {
|
||
|
|
val robots = robot.sorted()
|
||
|
|
val repairs =
|
||
|
|
factory.map { it ->
|
||
|
|
Factory(it[0], it[1])
|
||
|
|
}.sortedBy {
|
||
|
|
it.position
|
||
|
|
}.flatMap {
|
||
|
|
(1..it.limit).map { _ -> it.position }
|
||
|
|
}
|
||
|
|
|
||
|
|
val dp = Array(1 + robots.size) { LongArray(1 + repairs.size) }
|
||
|
|
// Base
|
||
|
|
robots.indices.forEach { i ->
|
||
|
|
dp[i][repairs.size] = 1L.shl(40)
|
||
|
|
}
|
||
|
|
|
||
|
|
product(robots.indices.reversed(), repairs.indices.reversed()).forEach { (i, j) ->
|
||
|
|
val assigning = abs(robots[i] - repairs[j]) + dp[i + 1][j + 1]
|
||
|
|
val skipping = dp[i][j + 1]
|
||
|
|
|
||
|
|
dp[i][j] = listOf(assigning, skipping).min()
|
||
|
|
}
|
||
|
|
|
||
|
|
return dp[0][0]
|
||
|
|
}
|
||
|
|
}
|