星际勘探者

题目分析

飞船从起点出发，依次经过编号 1 到 n 的小行星，每经过一颗小行星消耗 1 单位能量。飞船初始能量为 w，能量采集装置最多使用 k 次（即最多在 k 颗小行星上采集能量）。求探索过程中能达到的最大能量值。

思路：贪心 + 小根堆

核心观察：当飞船到达第 i 颗小行星时（1-indexed），已经消耗了 i 单位能量。如果在前 i 颗小行星中选择了一些进行采集，那么此时的能量为：

$ $w - i + \sum_{\text{已采集}}energy[j]$ $

要使某个时刻的能量最大，等价于：对于每个位置 i，在前 i 颗小行星的能量值中选出最大的（至多 k 个），使得 $w - i + \text{选出的能量之和}$ 最大。

贪心策略：

从左到右遍历每颗小行星，遇到正能量值就加入小根堆，并累加到 sum 中。
如果堆的大小超过 k，就弹出堆顶（最小值），从 sum 中减去。这样堆中始终维护的是当前见过的最大的 k 个正能量值。
在每个位置计算当前能量 $w - (i+1) + sum$ ，更新全局最大值。
初始答案为 w（不移动的情况）。

这种做法保证了在每个位置 i，我们都考虑了前 i 个小行星中能量值最大的 k 个，从而得到该位置能达到的最大能量。

样例验证：n=17, w=20, k=19。由于 k >= n，所有小行星都可以采集，总采集能量为 150，到最后一颗小行星时能量为 $20 - 17 + 150 = 153$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

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

    int n, w, k;
    cin >> n >> w >> k;
    vector<int> e(n);
    for(int i = 0; i < n; i++) cin >> e[i];

    long long ans = w;
    long long sum = 0;
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆

    for(int i = 0; i < n; i++){
        if(e[i] > 0){
            pq.push(e[i]);
            sum += e[i];
            if((int)pq.size() > k){
                sum -= pq.top();
                pq.pop();
            }
        }
        long long cur = (long long)w - (i + 1) + sum;
        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), w = sc.nextInt(), k = sc.nextInt();
        int[] e = new int[n];
        for (int i = 0; i < n; i++) e[i] = sc.nextInt();

        long ans = w;
        long sum = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            if (e[i] > 0) {
                pq.offer(e[i]);
                sum += e[i];
                if (pq.size() > k) {
                    sum -= pq.poll();
                }
            }
            long cur = (long) w - (i + 1) + sum;
            ans = Math.max(ans, cur);
        }

        System.out.println(ans);
    }
}

import heapq
import sys
input = sys.stdin.readline

def main():
    n, w, k = map(int, input().split())
    e = list(map(int, input().split()))

    ans = w
    s = 0
    pq = []  # 小根堆

    for i in range(n):
        if e[i] > 0:
            heapq.heappush(pq, e[i])
            s += e[i]
            if len(pq) > k:
                s -= heapq.heappop(pq)
        cur = w - (i + 1) + s
        if cur > ans:
            ans = cur
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const [n, w, k] = lines[0].split(' ').map(Number);
    const e = lines[1].split(' ').map(Number);

    class MinHeap {
        constructor() { this.h = []; }
        size() { return this.h.length; }
        push(v) {
            this.h.push(v);
            let i = this.h.length - 1;
            while (i > 0) {
                const p = (i - 1) >> 1;
                if (this.h[p] <= this.h[i]) break;
                [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
                i = p;
            }
        }
        pop() {
            const top = this.h[0];
            const last = this.h.pop();
            if (this.h.length > 0) {
                this.h[0] = last;
                let i = 0;
                while (true) {
                    let s = i, l = 2*i+1, r = 2*i+2;
                    if (l < this.h.length && this.h[l] < this.h[s]) s = l;
                    if (r < this.h.length && this.h[r] < this.h[s]) s = r;
                    if (s === i) break;
                    [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                    i = s;
                }
            }
            return top;
        }
    }

    const pq = new MinHeap();
    let ans = w;
    let sum = 0;

    for (let i = 0; i < n; i++) {
        if (e[i] > 0) {
            pq.push(e[i]);
            sum += e[i];
            if (pq.size() > k) {
                sum -= pq.pop();
            }
        }
        const cur = w - (i + 1) + sum;
        if (cur > ans) ans = cur;
    }

    console.log(ans);
});

复杂度分析

时间复杂度： $O(n \log k)$ ，遍历 n 颗小行星，每次堆操作 $O(\log k)$ 。
空间复杂度： $O(k)$ ，堆中最多存储 k 个元素。