2023.12.28每日一题

2023-12-28 20:48:55

LeetCode每日一题

2735.收集巧克力

2735. 收集巧克力 - 力扣(LeetCode)

介绍

看题目看不懂,在评论区看到一个大哥解释,瞬间明白了。

一张桌子上有n件商品围成一圈,每件都有一个价签,它们构成数组nums。除了按照价签上的价格买东西之外,你还可以花x块钱把桌子转一下,把每件商品都对应到下一个价签,问把每种商品买一遍最少花多少钱

给你一个长度为 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

思路

LeetCode看的思路,自己没啥思路,还是说自己算法太垃圾,还需多练

nums数组表示购买对应索引类型的巧克力所需要的代价,可以通过每次以代价x来改变(平移)nums数组的分布。

由于nums数组的长度为n,那么进行n次平移操作之后,进入循环。因此有意义的平移操作最多为n-1次。

那么可以使用一个数组costNums来记录每个类型的巧克力,在{0,1,2, …, n-1}次操作过程中购买所需的最小值。在k次操作完成后,将costNums累加并加上k*x,得到操作k次完成购买所需的总代价。

最后,在{0,1,2,…,n-1}次操作中,选择具有最小代价的那次操作。

代码

C++
class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
        int n = nums.size();
        vector<int> costNums(nums);  // 初始操作 0 次的成本
        long long totalCost = accumulate(costNums.begin(), costNums.end(), 0LL); // 初始总成本

        // enumerate 0 to n-1 times operation
        for (int k=1; k<n; k++){
            // 根据当前操作更新 costNums 数组
            for (int i=0; i<n; i++) {
                costNums[i] = min(costNums[i], nums[(i+k)%n]);
            }
            // 计算当前操作的总成本并与之前的总成本进行比较,保留最小的
            totalCost = min(totalCost, accumulate(costNums.begin(), costNums.end(), 0LL) + static_cast<long long>(k)*x);
        }
        return totalCost;
    }
};
Java
class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        int[] costNums = Arrays.copyOf(nums, n); // 初始操作 0 次的成本
        long totalCost = Arrays.stream(costNums).asLongStream().sum(); // 初始总成本

        for (int k = 1; k < n; k++) {
            // 根据当前操作更新 costNums 数组
            for (int i = 0; i < n; i++) {
                costNums[i] = Math.min(costNums[i], nums[(i + k) % n]);
            }

            // 计算当前操作的总成本
            long currentCost = Arrays.stream(costNums).asLongStream().sum() + (long) k * x;

            // 如果当前成本更小,更新总成本
            totalCost = Math.min(totalCost, currentCost);
        }

        return totalCost;
    }
}

文章来源:https://blog.csdn.net/ysk_0904/article/details/135277014
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。