智力大冲浪

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

按扣款降序用并查集占最晚空闲时段

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1426
// 题意：奖励 m 元，n 个小游戏各占一个时段，第 i 个要在 ti 之前完成否则扣 wi 元，求小伟最多能拿到多少钱。
// 思路：按扣款从大到小排序，用并查集给每个游戏安排「尽量靠后」的空闲时段。
// 1. 并查集的 find(x) 返回不超过 x 的最大空闲时段，0 表示没有空位。
// 2. 占用时段 p 后把 fa[p] 指向 find(p - 1)，下次再查就会跳过它。
// 3. 安排不下才扣钱，最后用 m 减去总扣款。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：要按扣款从大到小安排，先安排扣得多的，扣得少的排不上才损失最小。
// 易错点：时段从 1 开始编号，0 号要保留为「无空位」的哨兵。
#include <bits/stdc++.h>
using namespace std;
struct Game {
    int t, w;
};
vector<int> fa;
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(){
    int m, n;
    if(!(cin >> m)) return 0;
    if(!(cin >> n)) return 0;
    vector<Game> g(n);
    for(int i = 0; i < n; i++) cin >> g[i].t;
    for(int i = 0; i < n; i++) cin >> g[i].w;
    sort(g.begin(), g.end(), [](const Game& x, const Game& y){
        return x.w > y.w;
    });
    fa.resize(n + 1);
    for(int i = 0; i <= n; i++) fa[i] = i;
    long long fine = 0;
    for(int i = 0; i < n; i++){
        int p = find(g[i].t);
        if(p == 0) fine += g[i].w;
        else fa[p] = find(p - 1);
    }
    cout << m - fine << "\n";
    return 0;
}

智力大冲浪

正文

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