ZeroJudge 解題筆記：a520. 12416 - Excessive Space Remover

作者：王一哲
日期：2026年1月6日


ZeroJudge 題目連結：a520. 12416 - Excessive Space Remover

解題想法

這題要先排除特例，如果字串中所有的連續空格都是 1 格，不需要取代空格，印出 0 即可。 接下來用數學解。先計算連續空格的數量最大值 $imax$。 狀況1，如果 $imax = 2^n$，每取代一次會使 $imax$ 減半，共要取代 $n$ 次。例如 $imax = 16$，每次取代空格之後，$imax$ 分別變為 $8, 4, 2, 1$，共 4 次。 狀況2，如果 $2^{n-1} < imax < 2^n$，需要取代 $n$ 次。例如 $imax = 13$，每次取代空格之後，$imax$ 分別變為 $7, 4, 2, 1$，共 4 次。

Python 程式碼

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

import sys, math

for line in sys.stdin:
    s = line.rstrip()
    imax, cnt = 0, 0
    for c in s:
        if c.isspace():
            cnt += 1
        else:
            imax = max(imax, cnt)
            cnt = 0
    imax = max(imax, cnt)
    if imax == 1:
        print(0)
    else:
        print(math.ceil(math.log2(imax)))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 356 kB，通過測試。

#include <iostream>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s;
    while(getline(cin, s)) {
        int imax = 0, cnt = 0;
        for(char c : s) {
            if (isspace(c)) {
                cnt++;
            } else {
                imax = max(imax, cnt);
                cnt = 0;
            }
        }
        imax = max(imax, cnt);
        if (imax == 1) {
            cout << "0\n";
        } else {
            cout << ceil(log2(imax)) << "\n";
        }
    }
    return 0;
}