日期: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;
}
沒有留言:
張貼留言