「一本通 1.1 例 5」智力大冲浪

题目描述

有 $n$ 个游戏（ $n \leqslant 500$ ），第 $i$ 个游戏必须在第 $t_i$ 个时段结束前完成（ $1 \leqslant t_i \leqslant n$ ），每个时段只能完成一个游戏。未按期完成第 $i$ 个游戏会损失 $w_i$ 元（ $w_i$ 为自然数）。初始有 $m$ 元奖励，求合理安排后能保留的最多的钱（即最小化总扣款）。

思路

按期限从小到大排序，逐个尝试安排游戏，用小根堆维护已安排游戏的扣款数。若堆的大小超过当前期限，说明时段不够，弹出扣款最小的游戏（记为超期）。最终堆里保住的扣款总和最大，答案为 $m - (\sum w_i - \text{堆中总和})$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys
from heapq import heappush, heappop

def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m = next(data)   # 初始奖励
    n = next(data)   # 游戏数
    deadlines = [next(data) for _ in range(n)]   # 各游戏的规定完成期限
    fines = [next(data) for _ in range(n)]       # 各游戏超期扣款数

    # 按期限从小到大逐个尝试安排：小根堆里存“已安排”游戏的扣款数。
    # 若当前游戏安排不下（已安排数超过其期限 deadline），就淘汰堆里扣款最小的一个
    # （记为超期），保证最终扣款总和最小。
    heap: list[int] = []   # 已安排游戏的扣款数（小根堆）
    for deadline, fine in sorted(zip(deadlines, fines)):
        heappush(heap, fine)
        if len(heap) > deadline:                 # 时段不够，牺牲扣款最小的一个
            heappop(heap)

    penalty = sum(fines) - sum(heap)             # 未被安排的游戏才扣款
    print(m - penalty)

if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:22
 * update_at: 2026-10-05 23:22
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 505;

struct Game {
    int t; // 期限
    int w; // 扣款
} a[MAXN];

bool cmp(Game x, Game y) {
    return x.t < y.t;
}

int n;
ll m;
int heap[MAXN]; // 小根堆，存已安排游戏的扣款
int heap_size;  // 堆当前大小

void push(int x) {
    heap[++heap_size] = x;
    int i = heap_size;
    while (i > 1 && heap[i] < heap[i / 2]) {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

int pop() {
    int res = heap[1];
    heap[1] = heap[heap_size--];
    int i = 1;
    while (i * 2 <= heap_size) {
        int son = i * 2;
        if (son + 1 <= heap_size && heap[son + 1] < heap[son])
            son++;
        if (heap[son] < heap[i]) {
            swap(heap[son], heap[i]);
            i = son;
        } else break;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].t;
    for (int i = 1; i <= n; ++i) cin >> a[i].w;

    sort(a + 1, a + n + 1, cmp); // 按期限从小到大排序

    ll sum_w = 0; // 全部扣款总和
    for (int i = 1; i <= n; ++i) {
        sum_w += a[i].w;
        push(a[i].w);
        if (heap_size > a[i].t) { // 已安排数超过当前期限，淘汰扣款最小的
            pop();
        }
    }

    ll keep = 0; // 堆中保住的扣款总和
    for (int i = 1; i <= heap_size; ++i) keep += heap[i];

    cout << m - (sum_w - keep) << "\n";
    return 0;
}

「一本通 1.1 例 5」智力大冲浪

目录

题目描述

思路

参考代码