《算法集训传送门》

  ?引言

? ❄️我们的算法之路❄️?

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️?短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼?☀️
   ?二分，?贪心，?并查集，?二叉树，?图论，?深度优先搜索(dfs)，?宽度优先搜索（bfs），?数论，?动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！???

今日主题：优先队列

 ?⭐️第一题?

   ✨题目

      1.最后一块石头的重量

   ✨思路：

将所有石头的重量放入最大堆中。每次依次从队列中取出最重的两块石头 aa 和 bb，必有 a \ge ba≥b。如果 a>ba>b，则将新石头 a-ba−b 放回到最大堆中；如果 a=ba=b，两块石头完全被粉碎，因此不会产生新的石头。重复上述操作，直到剩下的石头少于 22 块。最终可能剩下 11 块石头，该石头的重量即为最大堆中剩下的元素，返回该元素；也可能没有石头剩下，此时最大堆为空，返回 00

   ✨代码：

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> q;
        for (int s: stones) {
            q.push(s);
        }

        while (q.size() > 1) {
            int a = q.top();
            q.pop();
            int b = q.top();
            q.pop();
            if (a > b) {
                q.push(a - b);
            }
        }
        return q.empty() ? 0 : q.top();
    }
};

 ?⭐️第二题?

   ✨题目

       2.装满杯子需要的最短总时长

   ✨思路：

若t是偶数,那么我们可以先把x和y互相匹配,次进行“内部消化”。操作过后有x+y=z,此时每次用一个x和一个x或y匹配即可。答案就是+2。若t是奇数,仍然先将x和y互相匹配;次进行“内部消化”。操作过后有x+y-1=z,此时每次用一个z和一个x或y匹配,剩下一杯无法匹配。答案就是+x+1。

   ✨代码：

class Solution {
public:
    int fillCups(vector<int>& amount) {
        sort(amount.begin(), amount.end());
        if (amount[0] + amount[1] <= amount[2]) return amount[2];
        else {
            int t = amount[0] + amount[1] - amount[2];
            return (t + 1) / 2 + amount[2];
        }
    }
};

 ?⭐️第三题?

   ✨题目

      3.移除石子的最大得分

   ✨代码：

class Solution:
    def maximumScore(self, a: int, b: int, c: int) -> int:
        a,b,c = sorted([a,b,c])
        if a+b <= c:
            return (a+b)
        else:
            return (a+b+c)//2

 ?⭐️第四题?

   ✨题目

      4.最低加油次数

   ✨代码：

class Solution {
    public int minRefuelStops(int t, int start, int[][] ss) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
        int n = ss.length, idx = 0;
        int remain = start, loc = 0, ans = 0;
        while (loc < t) {
            if (remain == 0) {
                if (!q.isEmpty() && ++ans >= 0) remain += q.poll();
                else return -1;
            }
            loc += remain; remain = 0;
            while (idx < n && ss[idx][0] <= loc) q.add(ss[idx++][1]);
        }
        return ans;
    }
}

?写在最后?：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！???