ZeroJudge 解題筆記：i070. 比對卡片 (Match)

作者：王一哲
日期：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=" ")  # 印出小的那個

寫法2，用兩個 for 迴圈向左、向右線性搜尋，使用時間約為 38 ms，記憶體約為 3.4 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]  # 目標
        p, q = n, n  # 儲存位置差的變數，先預設為 n
        for j in range(i, n):  # 從 i 開始向右找
            if b[j] == t:  # 找到 t
                p = j-i; break  # p 設定為 j-i
        for j in range(i, -1, -1):  # 從 i 開始向左找
            if b[j] == t:  # 找到 t
                q = i-j; break  # q 設定為 i-j
        if p == n and q == n:  # 如果 p, q 皆等於 n，t 不在 b 之中，印出 -1
            print(-1, end="\n" if i == n-1 else " ")
        else:  # 反之印出小的那個
            print(min(p, q), end="\n" if i == n-1 else " ")

寫法3，從左向右、從右向左各掃過一次，記錄 a[i] 前一次出現的位置，如果 a[i] 已經出現過就更新距離。理論上這個寫法比較快，但是這題的測資不太，看不出效果。使用時間約為 20 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)  # 牌的數量
    a = list(map(int, input().split()))  # 老師的牌
    b = list(map(int, input().split()))  # 孩童的牌
    pre = [-1]*53  # 每張牌前一次出現的位置，-1 代表還沒有出現過
    ans = [n]*n  # 答案，預設為過大的值 n，因為位置差為 0 ~ n-1
    for i in range(n):  # 依序檢查每張牌
        pre[b[i]] = i  # b[i] 的數字前一次出現為位為 i
        if pre[a[i]] != -1:  # 如果 a[i] 的數字之前已經出現過
            ans[i] = min(ans[i], abs(i - pre[a[i]]))  # 更新位置差
    for i in range(n-1, -1, -1):  # 反過來檢查每張牌
        pre[b[i]] = i  # b[i] 的數字前一次出現為位為 i
        if pre[a[i]] != -1:  # 如果 a[i] 的數字之前已經出現過
            ans[i] = min(ans[i], abs(i - pre[a[i]]))  # 更新位置差
    ans = list(map(lambda x : -1 if x == n else x, ans))  # ans 之中的 n 取代

最後兩行印出的部分也可以改寫成這樣，但是效率比較差，使用時間約為 40 ms，記憶體約為 3.4 MB，通過測試。

for i, t in enumerate(ans):
    print(-1 if t == n else t, end="\n" if i == n-1 else " ")

C++ 程式碼

寫法1，用兩個 for 迴圈向左、向右線性搜尋，使用時間約為 2 ms，記憶體約為 92 kB，通過測試。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int n;  // 牌的數量
    while(scanf("%d", &n) != EOF) {
        int a[n], b[n];  // 老師的牌，孩童的牌
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        for(int i=0; i<n; i++) scanf("%d", &b[i]);
        for(int i=0; i<n; i++) {  // 依序檢查每張牌
            int t = a[i], p = n, q = n;  // 目標，儲存位置差的變數，先預設為 n
            for(int j=i; j<n; j++) {  // 從 i 開始向右找
                if (b[j] == t) {  // 找到 t
                    p = j-i; break;  // p 設定為 j-i
                }
            }
            for(int j=i; j>=0; j--) {  // 從 i 開始向左找
                if (b[j] == t) {  // 找到 t
                    q = i-j; break;  // q 設定為 i-j
                }
            }
            if (p == n && q == n) {  // 如果 p, q 皆等於 n，t 不在 b 之中，印出 -1
                if (i == n-1) printf("-1\n");
                else printf("-1 ");
            } else {  // 反之印出小的那個
                if (i == n-1) printf("%d\n", min(p, q));
                else printf("%d ", min(p, q));
            }
        }
    }
    return 0;
}

寫法2，從左向右、從右向左各掃過一次，記錄 a[i] 前一次出現的位置，如果 a[i] 已經出現過就更新距離。理論上這個寫法比較快，但是這題的測資不太，看不出效果。使用時間約為 2 ms，記憶體約為 352 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 牌的數量
    while(cin >> n) {
        // 老師的牌，孩童的牌，答案，每張牌前一次出現的位置
        vector<int> a (n), b (n), ans (n, n), pre (53, -1);
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<n; i++) cin >> b[i];
        for(int i=0; i<n; i++) {  // 依序檢查每張牌
            pre[b[i]] = i;  // b[i] 的數字前一次出現為位為 i
            if (pre[a[i]] != -1) ans[i] = min(ans[i], abs(i - pre[a[i]]));  // 如果 a[i] 的數字之前已經出現過，更新位置差
        }
        for(int i=n-1; i>=0; i--) {  // 依序檢查每張牌
            pre[b[i]] = i; // b[i] 的數字前一次出現為位為 i
            if (pre[a[i]] != -1) ans[i] = min(ans[i], abs(i - pre[a[i]]));  // 如果 a[i] 的數字之前已經出現過，更新位置差
        }
        for(int i=0; i<n; i++) {  // 印出答案
            if (ans[i] == n) cout << "-1" << " \n"[i == n-1];
            else cout << ans[i] << " \n"[i == n-1];
        }
    }
    return 0;
}