算法-每天一道题（16）-奖学金

小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。现在他知道每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话，小v要花bi 的时间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。

输入描述:

第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，

接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1

输出描述:

一行输出答案。

输入例子:

5 10 9

0 5

9 1

8 1

0 1

9 100

输出例子:

43

C++

#include <iostream>
#include <vector>
using namespace std;

class Solustion
{
public:
    void getBest()
    {
        int n, r, avg;
        while (cin >> n >> r >> avg)
        {
            vector<int> grade(n); // 成绩
            vector<int> time(n); // 每一分花费的时间
            for (int i = 0; i<n; i++)
                cin >> grade[i] >> time[i];
            this->sort(grade, time, n); // 花费最小时间可以提高成绩的优先，排序，贪心

            int now_grade = 0;
            for (int i = 0; i<n; i++)
                now_grade += grade[i];
            int rest_grade = avg*n - now_grade;
            if (rest_grade <= 0)
            {
                cout << 0 << endl;
                continue;
            }

            long long min_time = 0; // 由于测试的用例比较大，需要设置为long long 类型
            int index = 0;
            while (true)
            {
                if (rest_grade == 0)
                    break;
                if (grade[index] < r) // 从性价比最高的课程开始复习的
                {
                    grade[index] += 1;
                    rest_grade -= 1;
                    min_time += time[index];
                }
                else // 如果复习到满分了，就换一门课程
                {
                    index++;
                    if (index >= n)
                        break;
                }
            }
            cout << min_time << endl;
            grade.clear();
            time.clear();
            min_time = 0;
            index = 0;
            now_grade = 0;
        }
    }

    void sort(vector<int> &grade, vector<int> &time, int n)
    {
        int temp;
        for (int i = 0; i<n; i++)
            for (int j = i; j<n; j++)
                if (time[i]>time[j])
                {
                    temp = time[i];
                    time[i] = time[j];
                    time[j] = temp;

                    temp = grade[i];
                    grade[i] = grade[j];
                    grade[j] = temp;
                }
    }
};

int main()
{
    Solustion s;
    s.getBest();
    return 0;
}

/*
解题思路：

简单的贪心算法，从最小时间花费的课程开始复习，
复习到满分之后就换另一门最小时间花费的课程
int min_time比较坑，由于累加之后超过的最大范围，需要设置为long long
*/