牛牛锻炼

[编程题]牛牛锻炼

热度指数：859 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛想成为牛国最健壮的牛牛。

于是它开始疯狂锻炼，锻炼牛角，锻炼牛肌肉，锻炼牛尾巴.......
假设牛牛现在有n个项目需要锻炼，每个项目牛教练会根据它的锻炼情况给它打分。
对于任意一个项目i分数不能超过目标分数ai。

牛牛已经锻炼了一段时间，对于第i个项目已经获得了bi分。
因为项目不同，所以每个项目牛牛想多获得一分所花费的时间也不一定相同，对于第i个项目，牛牛想多获得一分需要花费ci分钟。
牛牛之前给自己设立了一个小目标就是要所有项目的平均分要超过d。
问牛牛在目前情况下合理安排训练项目，达到目标最短还需要多少分钟？

示例1

输入

2,4,[4,5],[4,5],[2,3]

输出

示例2

输入

5,4,[5,6,5,6,5],[5,4,3,2,3],[2,1,7,2,5]

输出

备注:

给定一个整数n,表示有n个项目。
给定一个整数d,表示牛牛的目标分数。
给定a,b,c数组。

$1 \leq n\leq 10^{5}$ , $1 \leq d\leq 10^{5}$
$1 \leq b_{i} \leq a_{i} \leq 10^{5}$
$1 \leq c_{i}\leq 10^{2}$

算法知识视频讲解

C/C++

nbgao

struct P{
    int a, c;
}p[100003];
bool cmp(P p1, P p2){
    return p1.c < p2.c;
}
typedef long long ll;
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param d int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @param c int整型vector 
     * @return long长整型
     */
    long long solve(int n, int d, vector<int>& a, vector<int>& b, vector<int>& c) {
        ll m = (ll)n*(ll)d, s=0;
        for(int i=0;i<n;i++){
            p[i].a = a[i]-b[i];
            p[i].c = c[i];
            m -= b[i];
        }
        sort(p, p+n, cmp);
        if(m < 0)
            return 0;
        for(int i=0;i<n;i++){
            if(p[i].a >= m){
                s += m * p[i].c;
                break;
            }
            s += p[i].a * p[i].c;
            m -= p[i].a;
        }
        return s;
    }
};

发表于 2020-07-31 23:43:36 回复(0)

Python3

独特的小哥哥不放弃

import heapq
class Solution:
    def solve(self, n, d, a, b, c):
        spend = 0
        alreadyHave = 0
        h = []
        for each in list(zip(c, a, b)):
            heapq.heappush(h, each)
            alreadyHave += each[2]
        needScore = d * n - alreadyHave
        if needScore <= 0:
            return 0
        while needScore >= 0:
            temp = heapq.heappop(h)
            if temp[1] - temp[2] < needScore:
                needScore = needScore - (temp[1] - temp[2])
                spend = spend + temp[0] * (temp[1] - temp[2])
            else:
                spend = spend + needScore * temp[0]
                break
        return spend

发表于 2022-10-26 11:31:17 回复(0)

geneti7032

class P:
    def __init__(self, x=0, y=0):
        self.a = x
        self.c = y

class Solution:
    def solve(self , n , d , a , b , c ):
        # write code here
        p = []
        res, m = 0, n*d
        for i in range(n):
            tmp = P(a[i]-b[i], c[i])
            p.append(tmp)
            m -= b[i]
        if m<=0:
            return 0
        p.sort(key=lambda x:x.c)
        for i in range(n):
            if p[i].a>m:
                res += m*p[i].c
                m = 0
                break
            res += p[i].a*p[i].c
            m -= p[i].a
        return res

发表于 2021-07-08 13:10:56 回复(0)