哪家做网站的好,网址大全123上网导航网址,搜狐焦点石家庄房产网,建设银行网站用户名是什么意思LeetCode每日一题
2735.收集巧克力
2735. 收集巧克力 - 力扣#xff08;LeetCode#xff09;
介绍
看题目看不懂#xff0c;在评论区看到一个大哥解释#xff0c;瞬间明白了。 一张桌子上有n件商品围成一圈#xff0c;每件都有一个价签#xff0c;它们构成数组nums。…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 10001 nums[i] 1091 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(vectorint nums, int x) {int n nums.size();vectorint costNums(nums); // 初始操作 0 次的成本long long totalCost accumulate(costNums.begin(), costNums.end(), 0LL); // 初始总成本// enumerate 0 to n-1 times operationfor (int k1; kn; k){// 根据当前操作更新 costNums 数组for (int i0; in; i) {costNums[i] min(costNums[i], nums[(ik)%n]);}// 计算当前操作的总成本并与之前的总成本进行比较保留最小的totalCost min(totalCost, accumulate(costNums.begin(), costNums.end(), 0LL) static_castlong 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;}
}
