使用贪婪启发式方法解决分配问题

我正在尝试解决这个问题：https://open.kattis.com/problems/workstations

佩内洛普是新建超级计算机管理团队的一员。她的工作是为来这里的研究人员分配工作站在超级计算机上运行他们的计算。佩内洛普很懒，讨厌为即将到来的研究人员解锁机器。她可以解锁机器远离她的办公桌，但不觉得这卑微的工作与她的资格相匹配。她应该决定忽略吗她可以简单地要求研究人员不要这样做的安全准则在他们离开时锁定他们的工作站，然后分配新的研究人员到不再使用但仍然未锁定。这样，她只需要解锁每个工作站对于第一个使用它的研究人员来说，这将是一个巨大的改进佩内洛普。

不幸的是，未使用的工作站会自动锁定自己，如果它们未使用超过 M 分钟。工作站具有锁定了自己，佩内洛普必须为下一个研究人员再次解锁它使用它。给定到达和离开的确切时间表研究人员，你能告诉佩内洛普她可以节省多少解锁吗要求研究人员在离开时不要锁定他们的工作站并以最佳方式将到达的研究人员分配到工作站？您可能会假设始终有足够的工作站可用。

(请参阅链接，它有示例并且格式更好(。

我的方法是贪婪的算法。

我首先按末日排序。

我迭代记录给定工作时间的结束时间。对于新的工作时间，我找到最近的工作站，其结束时间小于此新工作时间的开始时间。如果没有，则无法利用解锁。

代码：

import java.util.*
import kotlin.math.max
private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readLong() = readLn().toLong() // single int
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints
private fun readLongs() = readStrings().map { it.toLong() } // list of longs

fun greedy(times: List<Pair<Long, Long>>, m: Long): Long {
val sortedTimes = times.sortedBy { it.second }
val counter = mutableMapOf<Long, Long>()
val treeSet = TreeSet<Long>()
var count: Long = 0
for (i in 0 until sortedTimes.size) {
val currentStart = sortedTimes[i].first
val prev = treeSet.lower(currentStart + 1)
if (prev != null && prev + m >= currentStart) {
counter[prev] = counter[prev]!! - 1
if (counter[prev]!! == 0.toLong()) {
treeSet.remove(prev)
}
count += 1
}
counter.putIfAbsent(sortedTimes[i].second, 0)
counter[sortedTimes[i].second] = counter[sortedTimes[i].second]!! + 1
treeSet.add(sortedTimes[i].second)
}
return count
}
fun main(args: Array<String>) {
val (n, m) = readLongs()
val times = mutableListOf<Pair<Long, Long>>()
for (i in 0 until n) {
val (start, extra) = readLongs()
val end = start + extra
times.add(Pair(start, end))
}
val ans = greedy(times, m)
println(ans)
}

这通过了示例，但在某些隐藏的测试用例上失败。

我希望得到一些关于如何改进算法的指示。

一个想法：

让 wa， wb 两个工作站免费/可用
研究员来了。
佩内洛普应该为工作站分配最靠近锁定的位置(她最大限度地减少了锁定机器的可能性(

计算并行使用的工作站的最大 k 个 (O(2nlog(2n
按到达时间对研究人员进行排序 O(nlog(n((
将每个研究人员分配到其工作站

工作站可以是：锁定、空闲(和将被锁定(、使用。

将工作站带到离锁最近的免费

位置那是：

min_{w in workstation} w.lockAt 
such that w.lockAt >= arrival + m

如果没有这样的机器，那么使用锁定的机器。无论。例如最小的锁(方便(。

为了存储机器，按lookAt排序的有序集将允许在o(klog(k((中进行维护

O(max(2nlog(2n( ， nklog(k((( 其中 k 是工作站的数量...

在我的土豆机器 O3cpp 上，我可以在大约 10 秒内进行 9^ 次迭代，所以(非常粗略( nklogk <= 10^9 给出大约 ~k = 10^3。

希望没有那么多机器

相关内容

最新更新

热门标签：