将到达楼层等价为每栋首层强制取,剩余额外层加入小根堆,维护最大价值
OJ: roj
题目 ID: 5009
难度:提高+/省选-
标签:贪心优先队列python
创建: 2026-10-08 09:05
更新: 2026-10-08 09:05
形式化题目
给定
- 在同一栋楼可以上下移动,花费 1 单位时间。可以通过大滑梯从顶层直接到 1 层,花费 1 单位时间。
- 在不同楼之间跳跃,从第
栋楼花费 1 单位时间到第 栋楼同层(若目标楼矮则落在其顶层)。 求最大总价值。
注意:测试数据由原作者生成(素材源包含 data.py),可能并非官方原始评测数据。
正解
思路
这道题等价于“鱼塘钓鱼”的升级版。到达第
问题转化为:在某个前缀
维护过程中每次计算当前前缀的最大收益,对所有能到达的前缀取最大值即可。
代码
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;
}复杂度
- 时间复杂度:
。遍历每栋楼时,将其“额外件”压入小根堆,总计最多入队 次,出队 次,每次操作 。 - 空间复杂度:
。堆中最多存储 个元素。
总结
利用等价转化的思想,把“跳跃”和“同楼层获取”转化为消耗同一预算的动作,巧妙地应用优先队列维护贪心选择,这正是经典“鱼塘钓鱼”问题的进阶应用。