class Solution {
public:
long long minCost(vector<int>& nums, int x) {
}
};
2735. 收集巧克力
给你一个长度为 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 <= 10001 <= nums[i] <= 1091 <= x <= 109原站题解
rust 解法, 执行用时: 52 ms, 内存消耗: 2.1 MB, 提交时间: 2023-12-28 00:05:43
impl Solution {
pub fn min_cost(nums: Vec<i32>, x: i32) -> i64 {
let n = nums.len();
// s[k] 统计操作 k 次的总成本
let mut s: Vec<i64> = (0..n).map(|i| i as i64 * x as i64).collect();
for i in 0..n { // 子数组左端点
let mut mn = nums[i];
for j in i..(n + i) { // 子数组右端点（把数组视作环形的）
mn = mn.min(nums[j % n]); // 维护从 nums[i] 到 nums[j] 的最小值
s[j - i] += mn as i64; // 累加操作 j-i 次的花费
}
}
*s.iter().min().unwrap()
}
}
javascript 解法, 执行用时: 140 ms, 内存消耗: 53.3 MB, 提交时间: 2023-12-28 00:05:08
/**
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
var minCost = function(nums, x) {
const n = nums.length;
const s = Array(n).fill(0); // s[k] 统计操作 k 次的总成本
for (let i = 0; i < n; i++) {
s[i] = i * x;
}
for (let i = 0; i < n; i++) { // 子数组左端点
let mn = nums[i];
for (let j = i; j < n + i; j++) { // 子数组右端点（把数组视作环形的）
mn = Math.min(mn, nums[j % n]); // 维护从 nums[i] 到 nums[j] 的最小值
s[j - i] += mn; // 累加操作 j-i 次的花费
}
}
return Math.min(...s);
};
golang 解法, 执行用时: 64 ms, 内存消耗: 6.3 MB, 提交时间: 2023-06-13 14:49:52
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 }
cpp 解法, 执行用时: 140 ms, 内存消耗: 58.7 MB, 提交时间: 2023-06-13 14:49:40
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);
}
};
java 解法, 执行用时: 37 ms, 内存消耗: 42.7 MB, 提交时间: 2023-06-13 14:49:27
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;
}
}
python3 解法, 执行用时: 3424 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-13 14:49:14
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)