日期:2025年4月6日
ZeroJudge 題目連結:i070. 比對卡片 (Match)
解題想法
題目的敘述是:對老師的每張卡片,孩童需找到自己的卡片中和老師卡片數字相同且位置差距最小的卡片。看起來應該是孩童依照自己手上的卡片,依序找每張卡片的數字是否有在老師手上的卡片之中,如果有則要找距離最近的卡片並記錄位置差;但如果以題目中範例的圖示來看則是反過來,老師依照自己手上的卡片,依序找每張卡片的數字是否有在孩童手上的卡片之中,如果有則要找距離最近的卡片並記錄位置差。
另外有一題進階版〈i164. 比對卡片(進階版)〉,測資大很多。
Python 程式碼
寫法1,用串列切片及 index 找索引值。使用時間約為 21 ms,記憶體約為 3.5 MB,通過測試。
import sys
for line in sys.stdin:
n = int(line) # 牌的數量
a = list(map(int, input().split())) # 老師的牌
b = list(map(int, input().split())) # 孩童的牌
for i in range(n): # 依序檢查每張牌
t = a[i] # 目標
if t not in b: # 如果 t 不在 b 之中,印出 -1
print(-1, end="\n" if i == n-1 else " ")
elif i == 0: # 編號 0,只要向右找,索引值等於位置差
if t not in b: print(-1, end=" ") # 如果 t 不在 b 之中,印出 -1
else: print(b.index(t), end=" ")
elif i == n-1: # 編號 n-1,只要向左找
if t not in b: print(-1) # 如果 t 不在 b 之中,印出 -1
else: print(b[::-1].index(t)) # 先將 b 反過來再找 t
else: # 編號在中間,向右、向左各找一次,取較小的值
left = b[:i+1][::-1] # 取 b[0] ~ b[i+1],再反向
right = b[i:] # 取 b[i] ~ b[n-1]
p, q = n, n # 儲存位置差的變數,先預設為 n
if t in right: p = right.index(t) # 向右找
if t in left: q = left.index(t) # 向左找
print(min(p, q), end=" ") # 印出小的那個