leetcode 每日一题 2023年12月28日 收集巧克力

题目

2735. 收集巧克力

给你一个长度为 n、下标从 0 开始的整数数组 nums，nums[i] 表示收集位于下标 i 处的巧克力成本。每个巧克力都对应一个不同的类型，最初，位于下标 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] <= 10^9
• 1 <= x <= 10^9

分析

1. nums[i] 表示收集位于下标 i 处的巧克力成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

2. 我们需要收集所有类型的的巧克力，这里所有类型的巧克力是类型没有发生变更之前的。
   例如nums[1,2,3,4]
   类型为0的经过1次变换变更为类型1 价格为2 原始类型依然是0 即类型0经过变换后价格为2。
   在例如类型3，经过1次变换后价格为0。

3. 我么可以使用成本x，修改所有**巧克力的类型，**即原来是i的类型，现在变成了（i+1) mod n的类型。举个例子：
   nums[1,2,3,4]:第一行是种类(i)，第二行是成本(nums[i])

   0	1	2	3
   1	2	3	4

   现在操作一次支付了代价x: 对所有的下标执行i = （i+1）mod n 类型发生了改变，但是种类对应的价格是不会发生变化的。括号里面是种类变更前。

   1（0）	2（1）	3（2）	0（3）
   2	3	4	1

   等价于：即对种类的改变可以改为对值的改变:nums[i]=nums[i+1 mod n]

   0	1	2	3
   2	3	4	1

4. 我们需要算出收集所有类型巧克力所需的最小成本。

5. 假设我们变换了k次，那么对于初始类型为i的巧克力，这个过程中可能得到的值是nums[i],nums[(i+1) mod n],?,nums[(i+k) mod n]
   我们需要在当中得到最小的值，就是第k次变换之后nums[i]的值。

6. k的大小：k一定是小于n的，因为当k=n时：num[(i+k) mod n]是没有发生任何改变的。
   所以k的取值范围是**[1,n-1]**

7. 总代价=购买代价+变换代价(kx)
   每次变换计算一次总代价
   得到ans_min = min(t1,t2,…,tk)

编码

有时候不会做其实是读不懂题目，emm。当然这个题的描述也有很大问题。

class Solution {
    public static long minCost(int[] nums, int x) {
        long ans = getTotal(nums);
        int n = nums.length;
        //初始购买代价
        int [] cost = Arrays.copyOf(nums,n);
        //用k指代更换的此时
        for (int k=1;k<n;k++){
            for (int i = 0; i < n; i++) {
                //在每次变换的过程中，把最小花费保留下来。
                cost[i] = Math.min(nums[(i+k)%n],cost[i]);
            }
            //购买代价+变换代价，
            long t1 = getTotal(cost)+ (long) x *k;
            ans = Math.min(ans,t1);
        }
        return ans;
    }
    //累加
    public static long getTotal(int [] arr){
        long tot = 0;
        for (int i : arr) {
            tot+=i;
        }
        return tot;
    }
}

交流

qq群: