题目:
这是他给出的接口:
class Solution { public: int fillCups(vector& amount) { } };
作为一个数学学渣,我想不出厉害的数学算法来解答(也看不懂)
所以就放弃思考,直接开冲。
解题思路:
根据题目可知,因为要返回最少的秒数,
所以每次装两杯水是最快的,
因此,我们可以直接开一个大堆,减去两个最多的杯数,再让秒数++,
而减到最后只剩两种情况:[1, 0, 0] 和 [0, 0, 0]
那就只需当top2为零就返回top1 + 秒数即可。
代码:
class Solution { public: int fillCups(vector& amount) { //使用优先级队列模拟一个大堆 //因为优先级队列会自动排好序 priority_queue q; //入队 for(const auto& e : amount) { q.push(e); } //记录秒数 int ans = 0; //循环 while(1) { //取出队列最大的两个数 int x1 = q.top(); q.pop(); int x2 = q.top(); q.pop(); //满足[1, 0, 0] 或 [0, 0, 0] if(x2 == 0) { return ans + x1; } //秒数++,减两杯 ans++, x1--, x2--; q.push(x1), q.push(x2); } //最后加个return过检查 return 1; } };
这样就过了。
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。