ZeroJudge 解題筆記：f929. 程式老師的作業

作者：王一哲
日期：2025年10月30日


ZeroJudge 題目連結：f929. 程式老師的作業

解題想法

這題如果直接用 index 或是 find 找陣列中第一個 0 的索引值，速度會太慢，無法通過最後一筆測資。用一個最小優先佇列儲存陣列中所有 0 的索引值，如果需要將第一個 0 改成指定的值時，從最小優先佇列取出開頭的資料就能找到要修改的索引值，速度快很多。

Python 程式碼

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

import sys, heapq

n = int(sys.stdin.readline())  # 陣列長度
arr = list(map(int, sys.stdin.readline().split()))  # 陣列內容
pq = [i for i, a in enumerate(arr) if a == 0]  # 所有 0 的索引值
m = int(sys.stdin.readline())  # m 次操作
lines = sys.stdin.readlines()  # 讀取所有剩下的資料
ans = []  # 答案
for line in lines:  # 依序讀取事先存在 lines 的資料
    cmd = list(map(int, line.split()))  # 指令
    if cmd[0] == 1:  # 如果指令開頭是 1
        if pq:  # 如果 pq 有資料
            idx = heapq.heappop(pq)  # 取出 pq 開頭的資料
            arr[idx] = cmd[1]  # 修改 arr[idx]
    elif cmd[0] == 2 and arr[cmd[1]] != 0:  # 如果指令開頭是 2 而且指定的位置不是 0
        arr[cmd[1]] = 0  # 將指定的位置改成 0
        heapq.heappush(pq, cmd[1])  # 將這個位置加入 pq
    elif cmd[0] == 3:  # 如果指令開頭是 3
        if pq: ans.append(str(pq[0]) + "\n")  # 如果 pq 有資料，將 pq 開頭的資料轉成字串加上 \n 存入 ans 
        else: ans.append("-1\n")  # 反之，將 -1\n 存入 ans
sys.stdout.write("".join(ans))  # 將 ans 的資料接成很長的字串再輸出

C++ 程式碼

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

#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

int main() {
    int n; scanf("%d", &n);
    int arr[n];
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0, a; i<n; i++) {
        scanf("%d", &a);
        arr[i] = a;
        if (a == 0) pq.push(i);
    }
    int m; scanf("%d", &m);
    for(int i=0, cmd; i<m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            int x; scanf("%d", &x);
            if (!pq.empty()) {
                int idx = pq.top(); pq.pop();
                arr[idx] = x;
            }
        } else if (cmd == 2) {
            int idx; scanf("%d", &idx);
            if (arr[idx] != 0) {
                arr[idx] = 0;
                pq.push(idx);
            }
        } else if (cmd == 3) {
            if (!pq.empty()) printf("%d\n", pq.top());
            else printf("-1\n");
        }
    }
    return 0;
}