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

Q1 2185. 统计包含给定前缀的字符串 (opens new window)

秒

class SolutionA {
    fun prefixCount(words: Array<String>, pref: String): Int {
        return words.count { it.startsWith(pref) }
    }
}

Q2 2186. 使两字符串互为字母异位词的最少步骤数 (opens new window)

按字母来就可以，都增加到最大的那一方。

class SolutionB {
    fun minSteps(s: String, t: String): Int {
        val a = IntArray(26)
        val b = IntArray(26)
        s.forEach {
            a[it - 'a']++
        }
        t.forEach {
            b[it - 'a']++
        }
        var ans = 0
        for (i in 0 until 26) {
            ans += maxOf(a[i], b[i]) * 2 - a[i] - b[i]
        }
        return ans
    }
}

Q3 2187. 完成旅途的最少时间 (opens new window)

简单二分，被数据坑傻了，改Long改了3次...

class SolutionC {
    fun minimumTime(time: IntArray, totalTrips: Int): Long {
        val r = 1L * time.maxOrNull()!! * totalTrips
        return biMin(1, r) { total ->
            var cur = 0L
            time.forEach {
                cur += total / it
            }
            cur >= totalTrips
        }
    }
}

Q4 2188. 完成比赛的最少时间 (opens new window)

需要转换下思路，用同一个轮胎跑，跑1~20圈的最小时间可以计算出来。然后再DP处理。

class SolutionD {
    fun minimumFinishTime(tires: Array<IntArray>, changeTime: Int, numLaps: Int): Int {
        val max = 20
        val a = LongArray(max + 1) { Int.MAX_VALUE.toLong() }
        for (i in tires.indices) {
            var cur = tires[i][0].toLong()
            var step = tires[i][0].toLong()
            for (j in 0 until max) {
                a[j + 1] = minOf(a[j + 1], 0L + changeTime + cur)
                step = minOf(step * tires[i][1], Int.MAX_VALUE.toLong())
                cur += step
            }
        }
        val dp = LongArray(numLaps + 1) { Long.MAX_VALUE }
        dp[0] = 0
        for (i in 0 until numLaps) {
            for (j in 0 until max) {
                if (i + j in dp.indices) {
                    dp[i + j] = minOf(dp[i + j], dp[i] + a[j])
                }
            }
        }
        return (dp.last() - changeTime).toInt()
    }
}