题意整理

  • 牛牛在锻炼,锻炼的项目有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.复杂度分析

  • 时间复杂度:优先队列插入和删除的时间复杂度都是,总共需要插入n个元素,所以时间复杂度是
  • 空间复杂度:需要额外大小为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数组进行排序,所以时间复杂度是
  • 空间复杂度:需要额外大小为的arr数组,所以空间复杂度是