题目 #

You are given a 0-indexed integer array nums of size n representing the cost of collecting different chocolates. Each chocolate is of a different type, and originally, the chocolate at ith index is of ith type.

In one operation, you can do the following with an incurred cost of x:

• Simultaneously change the chocolate of ith type to (i + 1)th type for all indexes i where 0 <= i < n - 1. When i == n - 1, that chocolate will be changed to type of the chocolate at index 0.

Return the minimum cost to collect chocolates of all types, given that you can perform as many operations as you would like.

Example 1:

Input: nums = [20,1,15], x = 5
Output: 13
Explanation: Initially, the chocolate types are [0,1,2]. We will buy the 1st type of chocolate at a cost of 1.
Now, we will perform the operation at a cost of 5, and the types of chocolates will become [2,0,1]. We will buy the 0th type of chocolate at a cost of 1.
Now, we will again perform the operation at a cost of 5, and the chocolate types will become [1,2,0]. We will buy the 2nd type of chocolate at a cost of 1.
Thus, the total cost will become (1 + 5 + 1 + 5 + 1) = 13. We can prove that this is optimal.

Example 2:

Input: nums = [1,2,3], x = 4
Output: 6
Explanation: We will collect all three types of chocolates at their own price without performing any operations. Therefore, the total cost is 1 + 2 + 3 = 6.

Constraints:

• 1 <= nums.length <= 1000
• $1 <= nums[i] <= 10^9$
• $1 <= x <= 10^9$

思路1 枚举操作次数 #

分析 #

• 每次操作，所有数字都会变，那么只能枚举操作次数，计算最小值
• 找一个数组记录从操作0次操作n次之间的最小值
• 每一次操作，算一边和，操作最多n次，找到和的最小值

代码 #

 1func minCost(nums []int, x int) int64 {
 2	n := len(nums)
 3	minNums := make([]int, n)
 4	copy(minNums, nums)
 5	var res int64 = math.MaxInt64
 6	for i := 0; i < n; i++ {
 7		var sum int64 = int64(i * x)
 8		for j, v := range minNums {
 9			k := (i + j) % n
10			minNums[j] = min(v, nums[k])
11			sum += int64(minNums[j])
12		}
13		if sum < res {
14			res = sum
15		}
16	}
17	return res
18}