ZeroJudge 解題筆記：k866. 8.運送隕石 (Delivery)

作者：王一哲
日期：2025年5月13日



ZeroJudge 題目連結：k866. 8.運送隕石 (Delivery)

解題想法

我用 priority queue 儲存隕石重量，每次處理最重的隕石，將重量除以 2 之後再放回 priority queue 之中，處理 m 次之後，priority queue 最上面的資料就是答案。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 22.2 MB，通過測試。

import sys, math, heapq

for line in sys.stdin:
    n, m = map(int, line.split())  # n 顆隕石，m 顆炸彈
    ws = []  # 每顆隕石的重量，為了將最大值放上面，要加負號
    for w in map(int, input().split()): heapq.heappush(ws, -w)
    for _ in range(m):  # 執行 m 次
        w = -heapq.heappop(ws)  # 取出最大值
        h = w/2  # 除以2
        heapq.heappush(ws, -h)  # 加入兩個 -h
        heapq.heappush(ws, -h)
    print(math.ceil(-ws[0]))

C++ 程式碼

這題用 float 過不了，要用 double。使用時間約為 28 ms，記憶體約為 3.8 MB，通過測試。

#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    int n, m;  // n 顆隕石，m 顆炸彈
    while(scanf("%d %d", &n, &m) != EOF) {
        priority_queue<double> ws;  //每顆隕石的重量，最大值放上面
        for(int i=0; i<n; i++) {
            int w; scanf("%d", &w);
            ws.push(static_cast<double>(w));
        }
        for(int i=0; i<m; i++) {  // 執行 m 次
            double w = ws.top(); ws.pop();  // 取出最大值
            double h = w/2;  // 除以2
            ws.push(h); ws.push(h);  // 加入兩個 h
        }
        printf("%d\n", static_cast<int>(ceil(ws.top())));
    }
    return 0;
}