描述

这是一篇面对初级coder的题解。
知识点：贪心
难度：二星

题解

题目：
有个项目需要锻炼，对于任意一个项目i分数不能超过目标分数。对于第i个项目已经获得了分。对于第i个项目，牛牛想多获得一分需要花费分钟。
要所有项目的平均分要超过d，达到目标最短还需要多少分钟？

分析：
本题可以用贪心的方式求解 因为必然是要优先练习提分快的科目
贪心算法简介：
贪心算法是指：在每一步求解的步骤中，它要求“贪婪”的选择最佳操作，并希望通过一系列的最优选择，能够产生一个问题的（全局的）最优解。
贪心算法每一步必须满足一下条件：
1、可行的：即它必须满足问题的约束。
2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。

3、不可取消：即选择一旦做出，在算法的后面步骤就不可改变了。

方法一：遍历求解

每一轮都遍历

找最小值并标记
图片说明
#include <limits.h>
class Solution {
public:
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        long long sum=0;//总分数
        for(int i=0;i<n;i++)
            sum+=b[i];//累加总分
        long long need = (long long) n * d - sum;//需要增加分值
        long long ans=0;//锻炼用时
        while(need> 0){
            int min=INT_MAX;
            int minnum=0;
            for(int i=0;i<n;i++){
                if(c[i]<min&&a[i]>b[i]){//最小值
                    minnum=i;//记录最小值
                    min=c[i];//记录最小值位置
                }
            }
            int dis=a[minnum]-b[minnum];
            if(need>=dis){//需求大于差值 全部累加
                    ans+=min*dis;//达到目标分数用时
                    need-=dis;//需求降低
                    b[minnum]=a[minnum];//提高分值 避免重复索引
            }
            else //需求小于差值
               return ans+=min*need;//只锻炼需要那部分
        }
        return ans;//返回总用时
    }
};

复杂度分析：
相当于冒泡排序，最坏情况下，需要进行次遍历 故时间复杂度
同时由于是冒泡排序（没有占用额外空间），故空间复杂度为
运行测试：
只能通过7个测点
运行时间 1001ms 超时
占用内存 6032KB

方法二：排序后贪心

首先对锻炼的项目的提升速度)进行排序，之后按进行提分，直到达到目标分数

同时为保证排序时不破坏对应关系，需要定义一个结构体类型完成排序 

struct target {//存储状态
    int dis;//提高空间
    int time;//用时
};
bool cmp(target a, target b){//自定义比较函数 便于排序
    return a.time<b.time;//由小到大排序
}
class Solution {
public:
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        vector<target> target(n);//待排序目标分值
        long long sum=0;//总分数
        for(int i=0;i<n;i++){
            target[i].time=c[i];//每分提高时间
            target[i].dis=a[i]-b[i];//可提高分值
            sum+=b[i];//累加总分
        }
        sort(target.begin(), target.end(),cmp);//排序
        int i=0;
        long long need = (long long) n * d - sum;//需要增加分值
        long long ans=0;//锻炼用时
        while(need> 0){
            if(target[i].dis>0){
                if(need>=target[i].dis){//需求大于差值 全部累加
                    ans+=target[i].time*target[i].dis;//达到目标分数用时
                    need-=target[i].dis;//需求降低
                }
                else //需求小于差值
                    return ans+=target[i].time*need;//只锻炼需要那部分
            }
            i++;//下一个项目
        }
        return ans;//返回总用时
        // write code here
    }
};

复杂度分析：
时间复杂度:快速排序时间复杂度,快速排序之后至少遍历n个数组一次复杂度，故总的时间复杂度为
空间复杂度：额外创建的数组大小为,快速排序造成的空间复杂度为，其余使用的空间都为常数，故总的时间复杂度为 忽略高阶小
运行测试：
运行时间 42ms 占用内存 5984KB

总结

  1. 贪心
  2. 排序
    各种排序算法的特性要熟练掌握化用
    图片说明