Medium

题目描述

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

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

  • 同时将所有巧克力的类型变更，具体是将第 i 种类型的巧克力变为第 ((i + 1) mod n) 种类型。

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

示例 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] <= 10^9
  • 1 <= x <= 10^9

解题思路

这道题的关键是理解旋转操作的本质。每次操作后，第 i 个位置的巧克力类型会变为 (i-k) mod n，其中 k 是操作次数。

我们可以枚举操作次数 k（从 0 到 n-1），对于每个 k：

  1. 执行 k 次操作的成本是 k * x
  2. 对于每种巧克力类型 type，我们需要找到经过 k 次操作后，哪个位置的成本最低来购买这种类型的巧克力

具体来说，对于类型 type 的巧克力，经过 k 次操作后：

  • 原本在位置 (type + k) % n 的巧克力现在变成了 type 类型
  • 原本在位置 (type + k + 1) % n 的巧克力现在也可能变成 type 类型（如果之前经过了足够的旋转）

为了优化，我们可以预处理每种类型在不同操作次数下的最低成本。对于每种类型，我们维护一个最小成本，随着操作次数增加，检查新位置的成本是否更低。

算法步骤：

  1. 初始化每种类型的最低成本为其原始位置的成本
  2. 枚举操作次数 k 从 0 到 n-1
  3. 对于每种类型，更新其在当前操作次数下的最低成本
  4. 计算总成本：k * x + 所有类型的最低成本之和
  5. 返回所有可能操作次数下的最小总成本

时间复杂度为 O(n²)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
        int n = nums.size();
        vector<int> minCost(n);
        
        // 初始化每种类型的最低成本
        for (int i = 0; i < n; i++) {
            minCost[i] = nums[i];
        }
        
        long long result = accumulate(minCost.begin(), minCost.end(), 0LL);
        
        // 枚举操作次数
        for (int k = 1; k < n; k++) {
            // 更新每种类型在k次操作后的最低成本
            for (int type = 0; type < n; type++) {
                int pos = (type + k) % n;
                minCost[type] = min(minCost[type], nums[pos]);
            }
            
            // 计算k次操作的总成本
            long long totalCost = (long long)k * x;
            for (int cost : minCost) {
                totalCost += cost;
            }
            
            result = min(result, totalCost);
        }
        
        return result;
    }
};

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        min_cost = nums[:]  # 每种类型的最低成本
        
        result = sum(min_cost)  # 0次操作的成本
        
        # 枚举操作次数
        for k in range(1, n):
            # 更新每种类型在k次操作后的最低成本
            for type_idx in range(n):
                pos = (type_idx + k) % n
                min_cost[type_idx] = min(min_cost[type_idx], nums[pos])
            
            # 计算k次操作的总成本
            total_cost = k * x + sum(min_cost)
            result = min(result, total_cost)
        
        return result

public class Solution {
    public long MinCost(int[] nums, int x) {
        int n = nums.Length;
        int[] minCost = new int[n];
        
        // 初始化每种类型的最低成本
        for (int i = 0; i < n; i++) {
            minCost[i] = nums[i];
        }
        
        long result = minCost.Sum(c => (long)c);
        
        // 枚举操作次数
        for (int k = 1; k < n; k++) {
            // 更新每种类型在k次操作后的最低成本
            for (int type = 0; type < n; type++) {
                int pos = (type + k) % n;
                minCost[type] = Math.Min(minCost[type], nums[pos]);
            }
            
            // 计算k次操作的总成本
            long totalCost = (long)k * x + minCost.Sum(c => (long)c);
            result = Math.Min(result, totalCost);
        }
        
        return result;
    }
}

var minCost = function(nums, x) {
    const n = nums.length;
    const minCost = [...nums];  // 每种类型的最低成本
    
    let result = minCost.reduce((sum, cost) => sum + cost, 0);
    
    // 枚举操作次数
    for (let k = 1; k < n; k++) {
        // 更新每种类型在k次操作后的最低成本
        for (let type = 0; type < n; type++) {
            const pos = (type + k) % n;
            minCost[type] = Math.min(minCost[type], nums[pos]);
        }
        
        // 计算k次操作的总成本
        const totalCost = k * x + minCost.reduce((sum, cost) => sum + cost, 0);
        result = Math.min(result, totalCost);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)外层循环 n 次操作，内层循环 n 种类型
空间复杂度O(n)存储每种类型的最低成本数组