ZeroJudge 解題筆記：i164. 比對卡片(進階版)

作者：王一哲
日期：2025年4月8日



ZeroJudge 題目連結：i164. 比對卡片(進階版)

解題想法

題目的敘述是：對老師的每張卡片，孩童需找到自己的卡片中和老師卡片數字相同且位置差距最小的卡片。看起來應該是孩童依照自己手上的卡片，依序找每張卡片的數字是否有在老師手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差；但如果以題目中範例的圖示來看則是反過來，老師依照自己手上的卡片，依序找每張卡片的數字是否有在孩童手上的卡片之中，如果有則要找距離最近的卡片並記錄位置差。 這題的基礎版為〈i070. 比對卡片 (Match)〉，測資小很多，用基本的寫法就能通過，但是這題不行。要從左向右、從右向左各掃過一次，記錄 a[i] 前一次出現的位置，如果 a[i] 已經出現過就更新距離。

Python 程式碼

使用時間約為 0.4 s，記憶體約為 35.8 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]*1000000  # 每張牌前一次出現的位置，-1 代表還沒有出現過，題目牌面編號最大值為 100000
    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 取代為 -1
    print(*ans)

C++ 程式碼

使用時間約為 64 ms，記憶體約為 5.3 MB，通過測試。

#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 (1000000, -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;
}