寿县网站建设,seo排名优化,长沙优化推广外包,企业网站建设 深圳2335. 装满杯子需要的最短总时长
题目描述
现有一台饮水机#xff0c;可以制备冷水、温水和热水。每秒钟#xff0c;可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount #xff0c;其中 amount[0]、amount[1] 和 a…2335. 装满杯子需要的最短总时长
题目描述
现有一台饮水机可以制备冷水、温水和热水。每秒钟可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。
给你一个下标从 0 开始、长度为 3 的整数数组 amount 其中 amount[0]、amount[1] 和 amount[2] 分别表示需要装满冷水、温水和热水的杯子数量。返回装满所有杯子所需的 最少 秒数。 示例 1
输入amount [1,4,2] 输出4 解释下面给出一种方案 第 1 秒装满一杯冷水和一杯温水。 第 2 秒装满一杯温水和一杯热水。 第 3 秒装满一杯温水和一杯热水。 第 4 秒装满一杯温水。 可以证明最少需要 4 秒才能装满所有杯子。 示例 2
输入amount [5,4,4] 输出7 解释下面给出一种方案 第 1 秒装满一杯冷水和一杯热水。 第 2 秒装满一杯冷水和一杯温水。 第 3 秒装满一杯冷水和一杯温水。 第 4 秒装满一杯温水和一杯热水。 第 5 秒装满一杯冷水和一杯热水。 第 6 秒装满一杯冷水和一杯温水。 第 7 秒装满一杯热水。 示例 3
输入amount [5,0,0] 输出5 解释每秒装满一杯冷水。 提示
amount.length 30 amount[i] 100
算法一贪心 数学思想
思路
将饮料按数量从大到小排序 设数量为 a b c 。如果 a b c 每次可以用一个 a 和 b / c 匹配 因此答案就是 a如果 a b c我们考虑超出的部分记为 dis b c - a。 如果 dis 是偶数那么我们可以先让 b 和 c 匹配 dis / 2 次 操作过后有 b c a 此时每次可以用一个 a 依次和 b / c 匹配 所以答案为 dis/2 a如果 dis 是奇数那么我们可以先让 b 和 c 匹配 dis-1 / 2 次 操作过后有 b c - 1 a 此时每次可以用一个 a 依次和 b / c 匹配 所以答案为 dis-1/ 2 a 上述两种情况可以合并为dis1 / 2 a 。
收获 这一题之前做过类似的1753. 移除石子的最大得分 。 因此做这道题的时候一直在回想之前是怎么完成的 但是一直没想出来最后想到了要分 a bc 和 a bc 两种情况但是第二种情况没有正确写出来。 查看了 1753 这道题后发现二者有些不同本题需要使数组中每个元素都为 0 而之前那道题只需要有 2 个元素为 0 。
算法情况
时间复杂度O1空间复杂度O1
代码
class Solution {
public:int fillCups(vectorint amount) {// 从大到小排序sort(amount.begin(), amount.end(), greater());int a amount[0], b amount[1], c amount[2];if(a b c) return a;else{int dis b c - a;return (dis 1) / 2 a;}}
};
