LeetCode每日一題

2735.收集巧克力

2735. 收集巧克力 - 力扣（LeetCode）

介紹

看題目看不懂，在評論區(qū)看到一個大哥解釋，瞬間明白了。

一張桌子上有n件商品圍成一圈，每件都有一個價簽，它們構成數組nums。除了按照價簽上的價格買東西之外，你還可以花x塊錢把桌子轉一下，把每件商品都對應到下一個價簽，問把每種商品買一遍最少花多少錢

給你一個長度為 n 、下標從 0 開始的整數數組 nums ，表示收集不同巧克力的成本。每個巧克力都對應一個不同的類型，最初，位于下標 i 的巧克力就對應第 i 個類型。

在一步操作中，你可以用成本 x 執(zhí)行下述行為：

• 同時修改所有巧克力的類型，將巧克力的類型 ith 修改為類型 ((i + 1) mod n)th。

假設你可以執(zhí)行任意次操作，請返回收集所有類型巧克力所需的最小成本。

示例 1：

輸入：nums = [20,1,15], x = 5
輸出：13
解釋：最開始，巧克力的類型分別是 [0,1,2] 。我們可以用成本 1 購買第 1 個類型的巧克力。
接著，我們用成本 5 執(zhí)行一次操作，巧克力的類型變更為 [1,2,0] 。我們可以用成本 1 購買第 2 個類型的巧克力。
然后，我們用成本 5 執(zhí)行一次操作，巧克力的類型變更為 [2,0,1] 。我們可以用成本 1 購買第 0 個類型的巧克力。
因此，收集所有類型的巧克力需要的總成本是 (1 + 5 + 1 + 5 + 1) = 13 ?？梢宰C明這是一種最優(yōu)方案。

示例 2：

輸入：nums = [1,2,3], x = 4
輸出：6
解釋：我們將會按最初的成本收集全部三個類型的巧克力，而不需執(zhí)行任何操作。因此，收集所有類型的巧克力需要的總成本是 1 + 2 + 3 = 6 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 109
• 1 <= x <= 109

思路

LeetCode看的思路，自己沒啥思路，還是說自己算法太垃圾，還需多練

nums數組表示購買對應索引類型的巧克力所需要的代價，可以通過每次以代價x來改變（平移）nums數組的分布。

由于nums數組的長度為n，那么進行n次平移操作之后，進入循環(huá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 operationfor (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;}
}