题解 | #牛牛锻炼#

题意

给定n个项目，每个项目有一定的分数可以获取，但获取一分的代价不同。目标是获取一定的分数，使平均值达到d.

方法一(暴力求解)

每个项目都能获取一定的分数，那么只要枚举每次通过哪个项目获取一分即可.

struct subject {    //项目 
    long long restPoint;    //还能得到多少分
    long long c;    //得到一分要花多少分种 
};
class Solution {
public:
    long long ans;
    vector<subject> objs;
    void dfs(int n,long long lastPoint,long long nowCost) {
        if (lastPoint == 0) {    //搞定 
            ans = min(ans,nowCost);
            return;
        }
        for (int i = 0;i < n;++ i) {
            if (objs [i].restPoint > 0) {    //还有可用的分数 
                -- objs [i].restPoint;    //减少 
                dfs(n,lastPoint - 1,nowCost + objs [i].c);
                ++ objs [i].restPoint;    //还原 
            }
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @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) {
        ans = 0x3f3f3f3f;
        // write code here
        objs.clear();
        long long nowCost = 0;
        long long targetPoint = d;    //离目标分数还差多少 
        targetPoint *= n;    //需要的总分 
        for (int i = 0;i < n;++ i) {
            subject tmp;
            tmp.c = c [i];
            tmp.restPoint = a [i] - b [i]; 
            targetPoint -= b [i];    //减掉已经获取的分数 
            objs.push_back(tmp);
        }
        if (targetPoint <= 0) {    //已经满足了，就不用再锻炼 
            return 0;
        }
        dfs(n,targetPoint,0);
        return ans;
    }
};

因为使用了dfs枚举每一个分数的来源，而每一个分数有n个来源，所以时间复杂度为 ,空间复杂度也为
显然会超时

方法二(贪心)

首先，平均值的定义为 ,将n乘到左边,即，等式右边即为总分。
显然，根据题意，要使平均分达到d,也就是总分要达到 。每一个项目获取到的分数没有差异。也就是说，从a项目获取一分，和从b项目获取一分，效果是一样的。那么显然，这个时候，获取一分的代价越低，花费的总时间也就越少。所以要尽量从代价低的分数开始。
也可以这么理解.
将每个项目比做水桶，而水桶内一开始就有一点水了且桶的体积不同。我们的目标是使总水量达到 ,而每个水桶内水的价格不同。为了使总价格最低，我们显然是优先选择水价低的桶尽可能的多加水。
所以我们可以在开始时以c为关键字进行排序，优先选择代价更小的项目锻炼。
注意，总分可能会爆int，所以最好使用long long.

struct subject {    //项目 
    long long restPoint;    //还能得到多少分
    long long c;    //得到一分要花多少分种 
};
bool cmp (const subject& a,const subject& b) {
    return a.c < b.c;
}
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) {
        // write code here
        vector<subject> objs;
        long long nowCost = 0;
        long long targetPoint = d;    //离目标分数还差多少 
        targetPoint *= n;    //目标分数
        for (int i = 0;i < n;++ i) {
            subject tmp;
            tmp.c = c [i];
            tmp.restPoint = a [i] - b [i];
            targetPoint -= b [i]; //减掉已经获取的分数 
            objs.push_back(tmp);
        }
        if (targetPoint <= 0) {
            return 0;
        }
        sort(objs.begin(),objs.end(),cmp);
        for (int i = 0;i < n;++ i) {
            if(targetPoint >= objs [i].restPoint) {    //全部都用掉 
                targetPoint -= objs [i].restPoint;
                nowCost += objs [i].c * objs [i].restPoint;
            } else {    // 这个项目剩下的分数绰绰有余。那就直接消耗掉所有的targetPoint 
                nowCost += objs [i].c * targetPoint;
                targetPoint = 0;
            }
            if (targetPoint == 0) {
                break;
            }
        }
        return nowCost;
    }
};

在这里，使用了排序，而后面的贪心步骤的时间复杂度为 ,所以总的时间复杂度为
因为只使用了vector存储项目，空间复杂度为