题解 | #牛牛锻炼#

题意整理

牛牛在锻炼，锻炼的项目有n个，a数组记录每个项目锻炼极限分数，b数组记录当前牛牛的得分，c数组记录每个项目多得一分需要得时间。
为了达到每个项目平均分大于等于d，牛牛至少还需要锻炼多长时间。

方法一（优先队列）

1.解题思路

可以定义一个int数组类型的优先队列，int数组长度为2，第一个元素存放每个项目多得一分所需时间，第二个元素存放每个项目还有多少分的上升空间，然后优先队列堆顶总是最小的第一个元素对应的数组。
每次取优先队列堆顶元素，如果当前得分总和加上堆顶元素对应的上升空间还小于目标分数，就加上对应的时间花费；如果大于等于目标分数，加上对应的时间花费，直接返回。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @param c int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int d, int[] a, int[] b, int[] c) {
        //初始化总得分和优先队列
        long sum=0;
        PriorityQueue<int[]> queue=new PriorityQueue<>((o1,o2)->o1[0]-o2[0]);
        for(int i=0;i<n;i++){
            queue.offer(new int[]{c[i],a[i]-b[i]});
            System.out.println(c[i]+"_"+(a[i]-b[i]));
            sum+=b[i];
        }

        //初始化时间消耗
        long time=0;
        while(!queue.isEmpty()){
            //每次选取时间消耗最小的那个项目
            int[] cur=queue.poll();
            //如果未达到目标分数，增加对应时间消耗
            if(sum+cur[1]<(long)d*n){
                sum+=cur[1];
                time+=cur[0]*cur[1];
            }
            //如果达到目标分数，增加对应时间消耗，直接返回
            else{
                time+=((long)d*n-sum)*cur[0];
                return time;
            }
        }

        return 0;
    }
}

3.复杂度分析

时间复杂度：优先队列插入和删除的时间复杂度都是 $O(log_2n)$ ，总共需要插入n个元素，所以时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外大小为n的优先队列，所以空间复杂度是 $O(n)$ 。

方法二（排序）

1.解题思路

定义一个二维int数组，第一列记录每个项目多得一分的时间花费，第二列记录每个项目的上升空间。然后按时间花费从小到大排序。
顺序遍历二维数组，如果当前得分总和加上当前的上升空间还小于目标分数，就加上对应的时间花费；如果大于等于目标分数，加上对应的时间花费，直接返回。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @param c int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int d, int[] a, int[] b, int[] c) {
        //初始化总得分
        long sum=0;
        for(int i=0;i<n;i++){
            sum+=b[i];
        }

        //初始化二维数组
        int[][] arr=new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=c[i];
            arr[i][1]=a[i]-b[i];
        }
        //按时间消耗排序
        Arrays.sort(arr,(o1,o2)->o1[0]-o2[0]);

        long time=0;
        //顺序遍历arr数组
        for(int i=0;i<n;i++){
            //如果未达到目标分数，增加对应时间消耗
            if(sum+arr[i][1]<(long)d*n){
                sum+=arr[i][1];
                time+=arr[i][0]*arr[i][1];
            }
            //如果达到目标分数，增加对应时间消耗，直接返回
            else{
                time+=((long)d*n-sum)*arr[i][0];
                return time;
            }
        }

        return 0;
    }
}

3.复杂度分析

时间复杂度：所有的遍历都是线性的，另外需要对arr数组进行排序，所以时间复杂度是 $O(nlog_2n)$ 。
空间复杂度：需要额外大小为 $2*n$ 的arr数组，所以空间复杂度是 $O(n)$ 。