第 222 场周赛题解

Q1 1710. 卡车上的最大单元数 (opens new window)

题目讲的比较啰嗦，其实就是贪心。按照单元数排序后从价值高的开始装箱子，直到箱子装完 or 卡车没地方为止。

class Solution1710 {
    fun maximumUnits(boxTypes: Array<IntArray>, truckSize: Int): Int {
        boxTypes.sortBy { -it[1] }
        var cur = truckSize
        var i = 0
        var ans = 0
        while (cur != 0 && i in boxTypes.indices) {
            val count = minOf(boxTypes[i][0], cur)
            ans += boxTypes[i][1] * count
            cur -= count
            i++
        }
        return ans
    }
}

Q2 1711. 大餐计数 (opens new window)

本质上就是两数之和，只是这次的和是$1..2^{21}$的2的幂。

import kotlin.math.pow

class Solution1711 {
    fun countPairs(deliciousness: IntArray): Int {
        val targets = (0..21).map { 2.0.pow(it).toInt() }
        val map = HashMap<Int, Int>()
        var ans: Long = 0
        for (i in deliciousness.indices) {
            for (target in targets) {
                ans += map[target - deliciousness[i]] ?: 0
            }
            map[deliciousness[i]] = map.getOrDefault(deliciousness[i], 0) + 1
        }
        ans %= (1e9 + 7).toLong()
        return ans.toInt()
    }
}

Q3 1712. 将数组分成三个子数组的方案数 (opens new window)

将数组分成三份，即需要插两个桩子。第一个桩子肯定需要从$0..lastIndex-1$完整遍历，第二个桩子若完整遍历则会超时，时间复杂度会达到$O(n^2)$。

由于数组元素非负，因此可以使用前缀和来优化。左侧的桩子遍历过程中，右侧的桩子是个持续的范围值，我们记为$(left,right)$，这样每对应一个左侧桩子，右边都会给结果增加$right-left+1$。可知，桩子增加时$left,right$都是单调递增的，因此整体时间复杂度为$O(n)$。

下面就是要考虑如何利用前缀和快速计算出$(left,right)$的范围。首先，第一部分的和为$sum[i]$，$left$的值为第一个$i$右边的值满足如下公式：

$$sum[left]-sum[i]>=sum[i]$$

而$right$右边的和为$total-sum[right]$，需要使右边部分大于等于中间部分，满足如下公式的最大值为$right$。

$$total-sum[right]>=sum[right]-sum[i]$$

具体代码如下，$r$的计算会默认比$right$ + 1，因此结果增加上更简洁。

class Solution1712 {
    fun waysToSplit(nums: IntArray): Int {
        val mod = 1000000007
        val sum = IntArray(nums.size + 1)
        for (i in nums.indices)
            sum[i + 1] = sum[i] + nums[i]
        var result = 0
        var l = 2
        var r = 3
        for (i in 1 until nums.size - 1) {
            l = maxOf(l, i + 1)
            while (l < nums.size && sum[l] - sum[i] < sum[i])
                l++
            r = maxOf(r, i + 1)
            while (r + 1 <= nums.size && sum.last() - sum[r] >= sum[r] - sum[i])
                r++
            if (l <= r)
                result = (result + r - l) % mod
        }
        return result
    }
}

Q4 1713. 得到子序列的最少操作次数 (opens new window)

这道题乍眼一看直接求出最长公共子序列，然后长度减一下即可，之后就LTE... 一看数据范围是$10^5$，再看看有没有别的条件，最后发现了重要的条件target中包含的元素各不相同，这样可以把这些元素按照其出现位置重新映射为自增，这样就从变成求最长公共子序列变为求最长递增子序列，时间复杂度从$O(n^2)$降低为$O(nlgn)$。

class Solution1713 {
    fun minOperations(target: IntArray, arr: IntArray): Int {
        val map = HashMap<Int, Int>()
        for (i in target.indices) {
            map[target[i]] = i
        }
        return target.size - arr.map {
            map.getOrDefault(it, -1)
        }.filter { it != -1 }.toIntArray().lis()
    }
}

fun IntArray.lis(): Int {
    var len = 1
    val n: Int = this.size
    if (n == 0) {
        return 0
    }
    val d = IntArray(n + 1)
    d[len] = this[0]
    for (i in 1 until n) {
        if (this[i] > d[len]) {
            d[++len] = this[i]
        } else {
            var l = 1
            var r = len
            var pos = 0
            while (l <= r) {
                val mid = l + r shr 1
                if (d[mid] < this[i]) {
                    pos = mid
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            d[pos + 1] = this[i]
        }
    }
    return len
}