Processing math: 100%

熱門文章

2025年4月27日 星期日

ZeroJudge 解題筆記:k468. 打靶 (Target)

作者:王一哲
日期:2025年4月27日



ZeroJudge 題目連結:k468. 打靶 (Target)

解題想法


我是用字典及 deque 儲存各類型的靶的位置,如果已經打掉就移除資料。

Python 程式碼


使用時間約為 32 ms,記憶體約為 5.8 MB,通過測試。
import sys
from collections import defaultdict, deque

for line in sys.stdin:
    n, s, f = map(int, line.split())  # n 個靶,要打第 s 個 f 類型標靶
    target = list(map(int, input().split()))  # 各位置標靶類型
    state = [True]*n  # 標靶是否還在
    pos = defaultdict(deque)  # 各類型標靶的位置
    for i, t in enumerate(target): pos[t].append(i)
    idx, cnt, hit = 0, 0, 0  # 目前要打的靶位置,射擊次數,打到目標類型標靶數量
    while idx < n:  # 當 idx 還沒有出界
        while not state[idx]: idx += 1  # 如果這個靶已經打掉,找下一個靶
        cnt += 1  # 射擊次數加 1
        now = target[idx]  # 目前打的標靶類型
        state[idx] = False  # 已打掉
        if now == f: hit += 1  # 打到 f 類型標靶,hit 加 1
        pos[now].popleft()  # 移除 now 對應的左側標靶位置
        if pos[now]:  # 如果 now 類型還有標靶
            state[pos[now].popleft()] = False  # 再移除最左側標靶位置,已打掉
            if now == f: hit += 1  # 打到 f 類型標靶,hit 加 1
        if hit >= s:  # 如果已打掉至少 s 個 f 類型標靶
            print(cnt); break  # 印出 cnt,中止迴圈


C++ 程式碼


使用時間約為 4 ms,記憶體約為 2.3 MB,通過測試。
#include <cstdio>
#include <unordered_map>
#include <queue>
using namespace std;

int main() {
    int n, s, f;  // n 個靶,要打第 s 個 f 類型標靶
    while(scanf("%d %d %d", &n, &s, &f) != EOF) {
        int target[n], state[n] = {0};  // 各位置標靶類型,標靶是否已被打落
        unordered_map<int, queue<int>> pos;  // 各類型標靶的位置
        for(int i=0; i<n; i++) {
            int t; scanf("%d", &t);
            target[i] = t;
            pos[t].push(i);
        }
        int idx = 0, cnt = 0, hit = 0;  // 目前要打的靶位置,射擊次數,打到目標類型標靶數量
        while(idx < n) {  // 當 idx 還沒有出界
            while(state[idx] == 1) idx++;  // 如果這個靶已經打掉,找下一個靶
            cnt++;  // 射擊次數加 1
            int now = target[idx];  // 目前打的標靶類型
            state[idx] = 1;  // 已打掉
            if (now == f) hit++;  // 打到 f 類型標靶,hit 加 1
            pos[now].pop();  // 移除 now 對應的左側標靶位置
            if (!pos[now].empty()) {  // 如果 now 類型還有標靶
                state[pos[now].front()] = 1;  // 再移除最左側標靶位置,已打掉
                pos[now].pop();
                if (now == f) hit++;  // 打到 f 類型標靶,hit 加 1
            }
            if (hit >= s) {  // 如果已打掉至少 s 個 f 類型標靶
                printf("%d\n", cnt); break;  // 印出 cnt,中止迴圈
            }
        }
    }
    return 0;
}


沒有留言:

張貼留言