ZeroJudge 解題筆記：j536. 不穩定的礦石 (Ore)

作者：王一哲
日期：2025年4月16日



ZeroJudge 題目連結：j536. 不穩定的礦石 (Ore)

解題想法

分成兩次檢查吸收能量的狀況比較好寫。

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n, a = map(int, line.split())  # n 個礦石，吸收力 a
    stone = list(map(int, input().split()))  # 礦石原來的能量
    p = stone.index(max(stone))  # 最多能量的礦石位置
    isum = sum(stone)  # 總能量
    cnt, imax = 0, stone[p]  # 已吸收的數量，吸收後的能量
    le = p - 1  # 向左吸收的位置
    # 向左吸收，最多吸收到位置 0 或是 p-a//2 為止，cnt 一定小於 a
    while le >= 0 and le >= p-a//2:
        cnt += 1; imax += stone[le]; le -= 1
    ri = p + 1  # 向右吸收的位置
    # 向右吸收，最多吸收到位置 n-1 或是 p+a//2 為止，cnt 一定小於 a
    while ri < n and ri <= p+a//2:
        cnt += 1; imax += stone[ri]; ri += 1
    # 第二次向左吸收，最多吸收到 cnt 等於 a 或是位置 0 
    while cnt < a and le >= 0:
        cnt += 1; imax += stone[le]; le -= 1
    # 第二次向右吸收，最多吸收到 cnt 等於 a 或是位置 n-1
    while cnt < a and ri < n:
        cnt += 1; imax += stone[ri]; ri += 1
    print(imax, isum-imax)  # 印出答案

C++ 程式碼

使用時間約為 7 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n, a;  // n 個礦石，吸收力 a
    while(scanf("%d %d", &n, &a) != EOF) {
        int stone[n], isum = 0, imax = 0, p = 0;  // 礦石原來的能量，總能量，最多能量的礦石及位置
        for(int i=0; i<n; i++) {
            int s; scanf("%d", &s);
            stone[i] = s; isum += s;
            if (s > imax) {
                imax = s; p = i;
            }
        }
        int cnt = 0, le = p-1, ri = p+1;  // 已吸收的數量，向左吸收的位置，向右吸收的位置
        // 向左吸收，最多吸收到位置 0 或是 p-a/2 為止，cnt 一定小於 a
        while(le >= 0 && le >= p-a/2) {
            cnt++; imax += stone[le]; le--;
        }
        // 向右吸收，最多吸收到位置 n-1 或是 p+a/2 為止，cnt 一定小於 a
        while(ri < n && ri <= p+a/2) {
            cnt++; imax += stone[ri]; ri++;
        }
        // 第二次向左吸收，最多吸收到 cnt 等於 a 或是位置 0 
        while(cnt < a && le >= 0) {
            cnt++; imax += stone[le]; le--;
        }
        // 第二次向右吸收，最多吸收到 cnt 等於 a 或是位置 n-1
        while(cnt < a && ri < n) {
            cnt++; imax += stone[ri]; ri++;
        }
        printf("%d %d\n", imax, isum-imax);  // 印出答案
    }
    return 0;
}