ZZU 月賽 C 題 Magnets 題解：統計磁鐵分組數量的簡單模擬

題目大意

有 n 塊磁鐵依次放置，每塊極性為 "01"（正負）或 "10"（負正）。相鄰磁鐵若極性相吸（前一塊右極與後一塊左極異名）則連成一組，否則分隔。求最終分組數。n ≤ 100000。

解題邏輯

第 i 塊磁鐵的左極為字符串首字符，右極為次字符。第 i 塊與第 i+1 塊屬於同一組，當且僅當第 i 塊的右極（str[1]）與第 i+1 塊的左極（next_str[0]）相同（異名相吸）。否則分組數加一。

算法

1. 讀入第一塊磁鐵，記錄其右極 cur = str[1]，分組數 ans = 1。
2. 循環讀入剩餘 n-1 塊：若 str[0] == cur，則 ans++ 並更新 cur = str[1]；否則只更新 cur = str[1]。
3. 輸出 ans。

AC 代碼 (C)

#include <stdio.h>
int main() {
    char a[3];
    int n;
    while (scanf("%d", &n) != EOF) {
        scanf("%s", a);
        n--;
        char cur = a[1];
        int ans = 1;
        while (n--) {
            scanf("%s", a);
            if (a[0] == cur) {
                ans++;
                cur = a[1];
            } else {
                cur = a[1];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

複雜度

時間 O(n)，空間 O(1)，極其高效。