第 276 场周赛题解 (opens new window)

Q1 2138. 将字符串拆分为若干长度为 k 的组 (opens new window)

模拟，这字符串操作还有点麻烦。

class SolutionA {
    fun divideString(s: String, k: Int, fill: Char): Array<String> {
        val arr = ArrayList<String>()
        var cur = 0
        while (cur * k in s.indices) {
            val a = s.substring(cur * k, minOf(s.length, (cur + 1) * k))
            arr.add(a.padEnd(k, fill))
            cur++
        }
        return arr.toTypedArray()
    }
}

Q2 2139. 得到目标值的最少行动次数 (opens new window)

贪心，能除以2就立刻除，这样肯定能省最多的步骤。

class SolutionB {
    fun minMoves(target: Int, maxDoubles: Int): Int {
        if (target == 1) return 0
        if (maxDoubles == 0) {
            return target - 1
        }
        if (target % 2 == 0) {
            return 1 + minMoves(target / 2, maxDoubles - 1)
        }
        // target % 2 != 0
        return 2 + minMoves(target / 2, maxDoubles - 1)
    }
}

Q3 2140. 解决智力问题 (opens new window)

标准DP，从后向前遍历。

class SolutionC {
    fun mostPoints(questions: Array<IntArray>): Long {
        val max = LongArray(questions.size)
        for (i in questions.indices.reversed()) {
            if (i + questions[i][1] + 1 in questions.indices) {
                max[i] = maxOf(max[i + 1], questions[i][0] + max[i + questions[i][1] + 1])
            } else if (i == questions.lastIndex) {
                max[i] = questions[i][0].toLong()
            } else {
                max[i] = maxOf(max[i + 1], questions[i][0].toLong())
            }
        }
        return max[0]
    }
}

Q4 2141. 同时运行 N 台电脑的最长时间 (opens new window)

想到了就很容易的题目。先将电池倒叙排序，然后每个电脑按顺序分配一个。若该电池大于当前总数的平均值，则该电池归该电脑用到最后（不需要其他电池来给它补充）。若最大值的电池也都小于平均值，那么结果就应该是这个平均值。

class SolutionD {
    fun maxRunTime(n: Int, batteries: IntArray): Long {
        batteries.sortDescending()
        var c = n
        var sum = 0L
        batteries.forEach {
            sum += it
        }
        batteries.forEach {
            if (it > sum / c) {
                c--
                sum -= it
            } else {
                return sum / c
            }
        }
        return -1
    }
}