algorithm - 优化算法以在4秒内运行大量操作

Question

我有以下代码用于解决practise challanges from hackerrank。

实际上，在列表中要创建10 ^ 7个值，然后应根据10 ^ 5个查询(包括控制台读取时间)对每个值进行递增，我需要在4秒钟内破解它。 Here是总输入(带有查询)。

第一行包含两个数字，first(n)是列表中值的数量，second(m)是下面紧跟的查询数量。下面的所有行都是3个数字，first(a)和second(b)是索引(从1开始)，third(k)是要添加到索引内的列表中的值。最后，列表中的最大值应该是控制台输出。

private fun readLn() = readLine()!! // string line
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

fun main() {
    val (n, m) = readInts()

    val list = MutableList(n) { 0L }
    repeat(m) {
        val queries = readStrings()
        val a = queries[0].toInt() - 1
        val b = queries[1].toInt() - 1
        val k = queries[2].toLong()

        for (i in a..b) {
            list[i] += k
        }
    }

    println(list.max())
}

目前，对我而言，它似乎已经过优化，但仍然无法在4秒内完成所有操作。

任何帮助将不胜感激，在此先感谢!

编辑-@Photon提供的答案后，我已经修改了代码，但仍然使用该算法，并且达到了相同测试用例的时间限制。

这是修改后的代码-

private fun readLn() = readLine()!! // string line
private fun readStrings() = readLn().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

fun main() {
    val (n, m) = readInts()

    val list = MutableList(n + 2) { 0L }
    repeat(m) {
        val queries = readStrings()
        val a = queries[0].toInt()
        val b = queries[1].toInt()
        val k = queries[2].toLong()

        list[a] += k
        list[b + 1] -= k
    }

    for (i in 1..n + 1) {
        list[i] = list[i - 1] + list[i]
    }

    println(list.max())
}

Answer 1

无论您如何优化，蛮力都太慢了。这是解决O(N + Q)时间的简单数组技巧:

首先，我们得到一个大小为N+2的零数组:A = [0, 0, 0, 0, ..., 0]

对于查询L R K而不是增加间隔中的所有数字，我们可以将第一个增加K，将R+1增加一个-K

，然后在所有查询之后，我们可以通过为A[i-1]中的所有i添加[1, N]来修改数组。

这与进行所有查询

相同

这可能令人困惑，所以这里有个例子:

N=5所以我们的初始数组:A = [0, 0, 0, 0, 0, 0, 0]

可以说我们有一个查询:1 3 3

更新的数组:A = [0, 3, 0, 0, -3, 0, 0]

可以说我们还有另一个查询:2 5 10

更新的数组:A = [0, 3, 10, 0, -3, 0, -10]

现在，在所有查询之后，我们可以为A[i-1]中的所有i添加[1, 5]

更新的数组:A = [0, 3, 13, 13, 10, 10, 0]

注意与通过蛮力

进行所有查询相同