2735-收集巧克力

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个长度为 n 、下标从 0 开始的整数数组 nums ，表示收集不同巧克力的成本。每个巧克力都对应一个不同的类型，最初，位于下标
i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

  • 同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

示例 1：

**输入：** nums = [20,1,15], x = 5
**输出：** 13
**解释：** 最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

**输入：** nums = [1,2,3], x = 4
**输出：** 6
**解释：** 我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • 1 <= x <= 109

下午两点【biIibiIi@灵茶山艾府】 直播讲题，记得关注哦~

提示 1

枚举操作次数。

提示 2

如果不操作，第 i 个巧克力必须花费 nums}[i] 收集，总成本为所有 nums}[i] 之和。

如果操作一次，第 i 个巧克力可以花费 \min(\textit{nums}[i], \textit{nums}[(i+1)\bmod n]) 收集。注意在求和的情况下，把题意理解成循环左移还是循环右移，算出的结果都是一样的。（样例 1 解释中的类型变更是反过来的，但计算结果是正确的。）

如果操作两次，第 i 个巧克力可以花费 \min(\textit{nums}[i], \textit{nums}[(i+1)\bmod n], \textit{nums}[(i+2) \bmod n]) 收集。

依此类推。

提示 3

如果暴力枚举，总的时间复杂度是 \mathcal{O}(n^3)。

优化办法有三种：

  1. 用 \mathcal{O}(n^2) 的时间预处理所有子数组的最小值，存到一个二维数组中。这样做需要 \mathcal{O}(n^2) 的空间。
  2. 用 ST 表优化上述过程。但还有更简单的做法。
  3. 用一个长为 n 的数组 sum 统计操作 i 次的总花费，这样就可以一边枚举子数组，一边求最小值，一边累加花费了。该方法只需要 \mathcal{O}(n) 的空间。
[sol-Python3]
1
2
3
4
5
6
7
8
9
class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        s = list(range(0, n * x, x))  # s[i] 对应操作 i 次的总成本
        for i, mn in enumerate(nums):  # 子数组左端点
            for j in range(i, n + i):  # 子数组右端点（把数组视作环形的）
                mn = min(mn, nums[j % n])  # 注：手动 if 比大小会快很多
                s[j - i] += mn  # 累加操作 j-i 次的成本
        return min(s)
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        var sum = new long[n];
        for (int i = 0; i < n; i++)
            sum[i] = (long) i * x; // 操作 i 次
        for (int i = 0; i < n; i++) { // 子数组左端点
            int mn = nums[i];
            for (int j = i; j < n + i; j++) { // 子数组右端点（把数组视作环形的）
                mn = Math.min(mn, nums[j % n]); // 从 nums[i] 到 nums[j%n] 的最小值
                sum[j - i] += mn; // 累加操作 j-i 次的成本
            }
        }
        long ans = Long.MAX_VALUE;
        for (var s : sum) ans = Math.min(ans, s);
        return ans;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    long long minCost(vector<int> &nums, int x) {
        int n = nums.size();
        long long sum[n];
        for (int i = 0; i < n; i++)
            sum[i] = (long long) i * x; // 操作 i 次
        for (int i = 0; i < n; i++) { // 子数组左端点
            int mn = nums[i];
            for (int j = i; j < n + i; j++) { // 子数组右端点（把数组视作环形的）
                mn = min(mn, nums[j % n]); // 从 nums[i] 到 nums[j%n] 的最小值
                sum[j - i] += mn; // 累加操作 j-i 次的成本
            }
        }
        return *min_element(sum, sum + n);
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func minCost(nums []int, x int) int64 {
	n := len(nums)
	sum := make([]int, n)
	for i := range sum {
		sum[i] = i * x // 操作 i 次
	}
	for i, mn := range nums { // 子数组左端点
		for j := i; j < n+i; j++ { // 子数组右端点（把数组视作环形的）
			mn = min(mn, nums[j%n]) // 从 nums[i] 到 nums[j%n] 的最小值
			sum[j-i] += mn // 累加操作 j-i 次的成本
		}
	}
	ans := math.MaxInt
	for _, s := range sum {
		ans = min(ans, s)
	}
	return int64(ans)
}

func min(a, b int) int { if b < a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n^2)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(n)。
 Comments
On this page
2735-收集巧克力
  1. 提示 1
  2. 提示 2
  3. 提示 3