楼间跳跃

GitHub跳转原题关系图返回列表

将到达楼层等价为每栋首层强制取,剩余额外层加入小根堆,维护最大价值

OJ: roj

题目 ID: 5009

难度:提高+/省选-

标签:贪心优先队列python

创建: 2026-10-08 09:05

更新: 2026-10-08 09:05

形式化题目

给定 nn 栋楼,第 ii 栋楼有 hih_i 层,每层有一件价值为 viv_i 的物品。 你在时间 mm 内移动,起初在第 1 栋楼顶。

  • 在同一栋楼可以上下移动,花费 1 单位时间。可以通过大滑梯从顶层直接到 1 层,花费 1 单位时间。
  • 在不同楼之间跳跃,从第 ii 栋楼花费 1 单位时间到第 i+1i+1 栋楼同层(若目标楼矮则落在其顶层)。 求最大总价值。

注意:测试数据由原作者生成(素材源包含 data.py),可能并非官方原始评测数据。

正解

思路

这道题等价于“鱼塘钓鱼”的升级版。到达第 kk 栋楼需 k−1k-1 次跳跃;进入每栋楼时落点所在层可免费取 1 件,楼内每再多取 1 件需 1 单位时间。如果在前缀 1…k1 \dots k 中每栋至少取 1 件,合计取 TT 件,则总时间恰为 T−1T-1(每多跳一栋消耗 1,每多取一件消耗 1)。因此,总件数不超过 m+1m+1。

问题转化为:在某个前缀 1…k1 \dots k 中,每栋先取 1 件(由于跳跃经过,可认为免费获得这 1 件),剩余的件数预算为 (m+1)−k(m+1) - k。其余件数按“每件价值 viv_i”贪心选最大的,用一个小根堆维护已选的“额外件”,如果当前维护的件数超过了预算,就从堆顶(价值最小的)开始淘汰。

维护过程中每次计算当前前缀的最大收益,对所有能到达的前缀取最大值即可。

代码

python
import sys
import heapq

def main():
    def get_ints():
        for line in sys.stdin:
            for token in line.split():
                yield int(token)

    tokens = get_ints()
    try:
        n = next(tokens)
        m = next(tokens)
    except StopIteration:
        return

    m += 1

    ans = 0
    sum_val = 0
    cnt = 0
    pq = []

    for i in range(1, n + 1):
        try:
            h = next(tokens)
            v = next(tokens)
        except StopIteration:
            break

        if i > m:
            break

        sum_val += v
        extra = h - 1
        if extra > 0:
            sum_val += extra * v
            cnt += extra
            heapq.heappush(pq, (v, extra))

        budget = m - i
        while pq and cnt - pq[0][1] >= budget:
            top_v, top_extra = heapq.heappop(pq)
            cnt -= top_extra
            sum_val -= top_extra * top_v

        if cnt > budget:
            over = cnt - budget
            ans = max(ans, sum_val - pq[0][0] * over)
        else:
            ans = max(ans, sum_val)

    print(ans)

if __name__ == '__main__':
    main()
cpp
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

static const int BUFSZ = 1 << 20;
static char ibuf[BUFSZ];
static int ipos = 0, ilen = 0;

static inline char getc() {
    if (ipos == ilen) {
        ilen = (int)fread(ibuf, 1, BUFSZ, stdin);
        ipos = 0;
        if (ilen == 0) return 0;
    }
    return ibuf[ipos++];
}

template <typename T>
static inline void readInt(T& x) {
    char c;
    do { c = getc(); } while (c != '-' && (c < '0' || c > '9'));
    int neg = 0;
    if (c == '-') { neg = 1; c = getc(); }
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getc();
    }
    if (neg) x = -x;
}

struct Node {
    long long h;
    long long v;
};

struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        return a.v > b.v;
    }
};

int main() {
    long long n, m;
    readInt(n);
    readInt(m);
    ++m;

    long long ans = 0;
    long long sum = 0;
    long long cnt = 0;
    priority_queue<Node, vector<Node>, Cmp> pq;

    for (long long i = 1; i <= n; ++i) {
        long long h, v;
        readInt(h);
        readInt(v);

        if (i > m) break;

        sum += v;
        long long extra = h - 1;
        if (extra > 0) {
            sum += extra * v;
            cnt += extra;
            pq.push(Node{extra, v});
        }

        long long budget = m - i;
        while (!pq.empty() && cnt - pq.top().h >= budget) {
            cnt -= pq.top().h;
            sum -= pq.top().h * pq.top().v;
            pq.pop();
        }
        
        if (cnt > budget) {
            long long over = cnt - budget;
            ans = max(ans, sum - pq.top().v * over);
        } else {
            ans = max(ans, sum);
        }
    }

    printf("%lld\n", ans);
    return 0;
}

复杂度

  • 时间复杂度:O(nlog⁡n)O(n \log n)。遍历每栋楼时,将其“额外件”压入小根堆,总计最多入队 nn 次,出队 nn 次,每次操作 O(log⁡n)O(\log n)。
  • 空间复杂度:O(n)O(n)。堆中最多存储 nn 个元素。

总结

利用等价转化的思想,把“跳跃”和“同楼层获取”转化为消耗同一预算的动作,巧妙地应用优先队列维护贪心选择,这正是经典“鱼塘钓鱼”问题的进阶应用。