题解 | #奖学金# 贪心

先按照复习的“性价比”排序，花较少单位时间的课程排在前面；

再计算出差多少分能够合格；

不断寻找能够补的课程并迭代缩小差距直至为0

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

int main() {
    int n, r, avg;
    while (cin >> n >> r >> avg) {
        vector<pair<long long, long long>> ab; // 记录每门课的平时成绩与时间的数对
        long long ai, bi;
        for (int i = 0; i < n; i++) {
            cin >> ai >> bi;
            ab.emplace_back(ai, bi);
        }
        // 按照复习所需时间从小到大排序
        sort(ab.begin(), ab.end(), [&](const auto & a, const auto & b) {
            return a.second < b.second;
        });
        // 当前平时成绩的总和
        long long currSum = 0;
        for (const auto & [a, b] : ab) {
            currSum += a;
        }
        // 还差多少分能合格
        long long diffSum = avg * n - currSum;
        // 记录复习用时
        long long time = 0;
        for (const auto & [a, b] : ab) {
            // 如果课程已满分，跳过
            if (a == r) {
                continue;
            }
            // 如果已经合格，跳出
            if (diffSum <= 0) {
                break;
            }
            // 如果还要补的分数大于等于当前课程能补的分数，则把当前课程补到满分
            // 如果还要补的分数小于当前课程能补的分数，则补足及格分即可
            if (diffSum >= r - a) { 
                diffSum -= r - a;
                time += (r - a) * b;
            } else {
                time += diffSum * b;
                break;
            }
        }
        cout << time << endl;
    }
    return 0;
}

时间复杂度：O(n)，用于遍历数对

空间复杂度：O(n)，用于存储数对