题解 | #牛牛锻炼#

思路：

题目的主要信息：

• 需要锻炼n个部位，每个部位现在打分记录在数组b中，最高可得分记录在数组a中，每个部位打分每增加1分需要花费的时间记录在数组c
• 求最少多久时间可以达到每个部位打分平均值达到d

方法一：贪心+排序
具体做法：
平均得分为d，就意味着总分必须不小于。
利用贪心思想，同样是增加1分，我们增加耗费时间较少的肯定最后总时间越少。因此我们可以将数组abc整合成一个结构，然后重载sor函数对其按照数组c递增排序，优先将耗费时间较少的增加到顶，依次增加，直到满足最后全部分数达到。

class Solution {
public:
    struct node{
        int a, b, c;
    };
    static bool comp(node& x, node& y){ //重载
        return x.c < y.c;
    }
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        vector<node> v;
        long long sum = 0;
        for(int i = 0; i < n; i++){
            v.push_back({a[i], b[i], c[i]});
            sum += b[i]; 
        }
        sort(v.begin(), v.end(), comp); //按照所需时间递增排序
        long long need = (long long) n * d - sum; //还需要多少
        long long res = 0;
        if(need > 0){
            for(int i = 0; i < n; i++){ //最前面的时间越少，先填满前面的
                if(need - (v[i].a - v[i].b) <= 0){ //够了
                    res += need * v[i].c;
                    return res;
                }
                else{
                    need -= v[i].a - v[i].b;
                    res += (v[i].a - v[i].b) * v[i].c;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，所有的循环只有，但是sort函数排序是
• 空间复杂度：，整合三个数组的结构数组v长度为

方法二：贪心+优先队列
具体做法：
利用方法一的贪心思想，重载一个小顶堆，堆顶是最小耗费时间，只要总分数还没达到，就不断弹出堆顶元素，增加这些耗费小的部位。

struct node{
   int a, b, c;
};
struct comp{
    bool operator()(node& x, node& y){ //重载priority_queue
        return x.c > y.c;
    }
};
class Solution {
public:
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        priority_queue<node, vector<node>, comp> pq; //c数组元素的小顶堆
        long long res = 0;
        long long sum = 0;
        for(int i = 0; i < n; i++){
            pq.push({a[i], b[i], c[i]}); //入堆
            sum += b[i]; //统计现有分数和
        }
        long long need = (long long) n * d - sum; //还差多少
        if(need > 0){
            for(int i = 0; i < n; i++){
                node p = pq.top(); //每次加最小的
                pq.pop();
                if(need <= p.a - p.b){ //够了
                    res += need * p.c;
                    return res;
                }else{
                    need -= p.a - p.b;
                    res += (p.a - p.b) * p.c;
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，前一个循环一共次，其中入堆每次需要，后一个循环最坏次，舍去低次幂
• 空间复杂度：，优先队列最长为数组长度