题解 | #牛牛锻炼#

题意：
有n个项目，第i个项目最多达到的分数为 ,现第i个项目已经有分数 ,每增加一份所花费时间为 如果所有项目的平均分要达到d，需要最少多少时间

方法一：贪心+自定义排序函数

• 当所有项目达到平均分d时项目分数总和为,而现在拥有的分数scores=sum()(i从0到n),则现在需要增加的分数
• 如何使得所需时间最短呢？因为增加一分的的代价不相等，要想达到需要分数，我们应该先花费时间做代价小的相项目，因此定义一个项目类，类中包含当前项目剩余可增加的分数restScore和增加一分花费时间c，将项目数组按照代价c从小到大排序
• 遍历项目组，如果当前项目组剩余可增加分数已经小于或者等于需要的分数，则直接计算并返回时间，否则每次都将当前项目的可增加分数乘以它的代价，并且减掉相应的需要分数

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @param c int整型一维数组 
     * @return long长整型
     */

    class Project{
        int restScore,c;//剩余可增加的分数和花费时间
        Project(int restScore,int c){
            this.restScore=restScore;
            this.c=c;
        }

    }
    public long solve (int n, int d, int[] a, int[] b, int[] c) {
        // write code here
        Project[]p=new Project[n];
        long scores=0;
        for(int i=0;i<n;i++){
            p[i]=new Project(a[i]-b[i],c[i]);
            scores+=b[i];//最初的分数和
        }
        long need=(long)d*n-scores;//还需要增长的分数，注意转为long类型，否则会造成数据溢出
        if(need==0)return 0;//还需要分数为0返回0
        Arrays.sort(p,new Comparator<Project>(){
            public int compare(Project p1,Project p2){
                return p1.c-p2.c;
            }
        });//递增排序，最小花费时间的排在前面
        long time=0;
        for(int i=0;i<n;i++){
            if(need-p[i].restScore<=0){
                time+=need*p[i].c;//如果还需要增长的分数小于当前项目所需要分数则当前项目为最后一个需要做的项目，返回总时间
                return time;
            }else{
                time+=p[i].restScore*p[i].c;//否则继续让当前项目剩余可增长分数乘以需要的时间并累加时间，所需分数相应减少
                need-=p[i].restScore;
            }
        }return 0;
    }
}

复杂度：
时间复杂度:, 至少遍历n个数组一次,并且排序数组的时间复杂度为
空间复杂度：,额外创建的项目数组大小不超过n

方法二：贪心+最小堆
可以将项目组存储在最小堆中，这时候需要自定义比较器以c排序，c最小的位于堆顶，每次都让堆顶元素出队

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @param c int整型一维数组 
     * @return long长整型
     */

    class Project{
        int restScore,c;//剩余可增长的分数和花费时间
        Project(int restScore,int c){
            this.restScore=restScore;
            this.c=c;
        }
    }
    //自定义比较器
    public static Comparator<Project> cComparator = new Comparator<Project>(){
        @Override
        public int compare(Project p1, Project p2) {
            return p1.c - p2.c;
        }
    };
    public long solve (int n, int d, int[] a, int[] b, int[] c) {
        // write code here
        PriorityQueue<Project>q=new PriorityQueue<>(cComparator);//用自定义的比较器创建优先级队列（最小堆）
        long scores=0;
        for(int i=0;i<n;i++){
            q.offer(new Project(a[i]-b[i],c[i]));
            scores+=b[i];
        }
        long need=(long)d*n-scores;//还需要分数
        if(need==0)return 0;//还需要分数为0返回0
        long time=0;
        for(int i=0;i<n;i++){
            Project get=q.poll();//弹出c最小的项目
            if(need<=get.restScore){//如果还需要增长的分数小于当前项目所需要分数则当前项目为最后一个需要做的项目，返回总时间
                time+=need*get.c;
                return time;
            }else{
                time+=get.restScore*get.c;//否则继续让当前项目剩余可增长分数乘以需要的时间并累加时间，所需分数相应减少
                need-=get.restScore;
            }
        }return 0;
    }
}

复杂度：
时间复杂度：优先级队列出队入队的时间复杂度为 ,而且有一层循环，因此时间复杂度为
空间复杂度：队列大小不超过n，因此空间复杂度为