贪心算法解决作业安排问题：最小化逾期扣分

小明上学，老师布置了 n 个作业，每个作业恰好需要一天做完，每个作业都有最后提交时间 ti 及其逾期的扣分 ki。已知作业 n = 3，每个作业的最后提交时间 t = [1, 3, 1]，作业逾期扣分 k = [6, 2, 3]。以输入 n = 0 时作为结束，请给出小明做作业的顺序，以便扣最少的分数。

贪心算法内容

可以采用贪心算法来解决这个问题。我们可以将作业按照最后提交时间从小到大排序，如果最后提交时间相同，则按照逾期扣分从小到大排序。每次选择最早的作业来做，这样可以让后面的作业有更多的时间来完成，从而减少逾期扣分。

具体实现过程

将作业按照最后提交时间从小到大排序。
对于最后提交时间相同的作业，按照逾期扣分从小到大排序。
按照排序后的顺序依次完成作业。

代码实现

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

struct Homework {
    int t;  // 最后提交时间
    int k;  // 逾期扣分
};

bool cmp(Homework a, Homework b) {
    if (a.t == b.t) {
        return a.k < b.k;
    }
    return a.t < b.t;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        Homework h[n];
        for (int i = 0; i < n; i++) {
            cin >> h[i].t >> h[i].k;
        }
        sort(h, h + n, cmp);
        int day = 0;
        int score = 0;
        for (int i = 0; i < n; i++) {
            day += 1;
            if (day > h[i].t) {
                score += h[i].k;
            }
        }
        cout << score << endl;
    }
    return 0;
}

输入样例

输出样例