题意分析

  • 一共有个项目，每个项目的得分上线为。
  • 现在已经每个项目已经得到的分数了。
  • 每个项目对应的得分为。
  • 给定一个,我们想要总的得分得到最少还需要多少时间。

思路分析

  • 贪心。我们很容易可以想到，如果想花费的时间最少，肯定实现做训练时间短的项目。所以，我们计算每个项目还可以得到的分数和这个项目得到一份所需要的时间。然后按照时间进行排序。最后按照时间的小到大进行贪心即可。我们优先完成时间段的任务。直到可以到达最高得分即可。注意一下开。

  • 这里我们增加一个对样例2的解释

图片说明

写法一 C++版

  • 的写法没有什么说法。直接在结构体里面重载排序函数即可。

  • 代码如下

    • 需要从1-n进行遍历，时间复杂度为
    • 用结构体存储每个训练项目的时间和还剩的分数，空间复杂度为 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @param c int整型vector 
     * @return long长整型
     */
    typedef long long ll;
    struct node{
        ll x;
        ll t;
        bool operator < (const node &b){
            return t<b.t;
        }
    }Node[100010];
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        // write code here
        ll sum=0;
        for(auto x:b){
            sum+=x;
        }
        ll res=(ll)n*d;
        for(int i=0;i<n;i++){
            Node[i].x=a[i]-b[i];
            Node[i].t=c[i];
        }
        if(sum>=res){
            return 0;
        }
        sort(Node,Node+n);
//         for(int i=0;i<n;i++){
//             std::cout<<Node[i].x<<" "<<Node[i].t<<endl;
//         }

        ll ans=0;
        for(int i=0;i<n;i++){
            if(Node[i].x+sum>=res){
                ans+=(res-sum)*Node[i].t;
                break;
            }else{
                ans+=Node[i].x*Node[i].t;
                sum+=Node[i].x;
            }
        }

        return ans;
    }
};

写法二 Go语言版

  • Go语言版需要重写一些接口。先把切片数组定义成一个类型，然后重写Len,Swap和Less函数即可。其他的和C++的写法基本一样。

  • 代码如下

    • 需要从1-n进行遍历，时间复杂度为
    • 用结构体存储每个训练项目的时间和还剩的分数，空间复杂度为 
package main
import "sort"
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param d int整型 
 * @param a int整型一维数组 
 * @param b int整型一维数组 
 * @param c int整型一维数组 
 * @return long长整型
*/
type node struct {
    num int64
    tim int64
}
// 先要将这个切片数组定义成一个类型
type NodeSlice []node
// 然后重写一些基本的方法
func (a NodeSlice) Len() int {
    return len(a)
}
func (a NodeSlice) Swap(i, j int) {
    a[i], a[j] = a[j], a[i]
}
// 按照时间的大小进行排序
func (a NodeSlice) Less(i,j int) bool{
    return a[i].tim < a[j].tim
}
func solve( n int ,  d int ,  a []int ,  b []int ,  c []int ) int64 {
    // write code here
    var Node = make([]node,n)
    var sum int64
    for _,val := range b {
        sum=sum+int64(val)
    }
    var res int64
    res=int64(n*d)
    // 特判不用继续训练的情况
    if res <= sum {
        return 0
    }
    for i:=0; i<n; i++ {
        Node[i].num=int64(a[i]-b[i])
        Node[i].tim=int64(c[i])
    }
    // 进行排序
    sort.Sort(NodeSlice(Node))
    var ans int64
    for i:=0; i < n; i++ {
        // 如果此时这个项目足够了，那么计算还差多少就行了
        if sum+Node[i].num>=res {
            ans+=int64(res-sum)*Node[i].tim
            break
        }else{
            ans+=Node[i].num*Node[i].tim
            sum+=Node[i].num
        }
    }

    return ans;

}