家庭作业

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1026 字

按学分降序用并查集占最晚可用日期

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1430
// 题意：n 个作业各有截止日期和学分，每个作业耗时一天，求在截止日期前完成能拿到的最大学分。
// 思路：按学分从大到小排序，用并查集把每个作业安排到不超过其截止日期的最晚空闲天。
// 1. find(x) 返回不超过 x 的最大空闲天，0 表示排满了。
// 2. 学分高的优先占坑，占不到就放弃这个作业。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：截止日期可能大于 n，但最多只可能完成 n 个作业，所以把日期截断到 n 再并查集，省内存也安全。
// 易错点：按学分降序贪心即可，不必按截止日期排序；反过来先排日期会丢最优解。
#include <bits/stdc++.h>
using namespace std;
struct Work {
    int d, v;
};
vector<int> fa;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(){
    int n;
    if(!(cin >> n)) return 0;
    vector<Work> w(n);
    for(int i = 0; i < n; i++) cin >> w[i].d >> w[i].v;
    sort(w.begin(), w.end(), [](const Work& x, const Work& y){
        return x.v > y.v;
    });
    fa.resize(n + 1);
    for(int i = 0; i <= n; i++) fa[i] = i;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        int d = min(w[i].d, n);
        int p = find(d);
        if(p > 0){
            ans += w[i].v;
            fa[p] = find(p - 1);
        }
    }
    cout << ans << "\n";
    return 0;
}

家庭作业

正文

一本通·提高篇的其它内容