ZeroJudge 解題筆記：f374. 分組 Grouping

作者：王一哲
日期：2025年3月7日



ZeroJudge 題目連結：f374. 分組 Grouping

解題想法

這題在 Python 我是用 enumerate 搭配字串切片 [::-1] 反向讀取字元，在 C++ 則是用索引值從字串中讀取字元。

Python 程式碼

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

import sys

for line in sys.stdin:
    n, s = line.split()  # 將 line 分割成每組人數 n、戰力 s
    n = int(n)  # 將 n 轉成整數
    idx, imax = 0, 0  # 最大戰力組別、戰力
    group, tot = 1, 0  # 目前的組別、戰力
    for i, c in enumerate(s[::-1]):  # 從 s 最後面往前讀取
        tot += int(c)  # 將 c 轉成整數加到 tot
        if (i+1)%n == 0 or i == len(s)-1:  # 如果 (i+1) 可以被 n 整除或是 i 等於 len(s)-1，檢查小組戰力
            if tot >= imax:  # 如果 tot 大於等於 imax
                imax = tot  # imax 更新為 tot
                idx = group  # idx 更新為 group
            tot = 0; group += 1  # tot 歸零，group 加 1
    print(f"{idx:d} {imax:d}")  # 印出答案

C++ 程式碼

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; string s;  // 每組人數 n、戰力 s
    while(cin >> n >> s) {
        int idx = 0, imax = 0, group = 1, tot = 0, m = (int)s.size();   // 最大戰力組別、戰力，目前的組別、戰力，總人數
        for(int i=m-1; i>=0; i--) {  // 從 s 最後面往前讀取
            tot += s[i] - '0';  // 將 s[i] 轉成整數加到 tot
            if ((m-i)%n == 0 || i == 0)  {  // 如果 m-i 可以被 n 整除或是 i 等於 0，檢查小組戰力
                if (tot >= imax) {  // 如果 tot 大於等於 imax
                    imax = tot;  // imax 更新為 tot
                    idx = group;  // idx 更新為 group
                }
                tot = 0; group++;  // tot 歸零，group 加 1
            }
        }
        cout << idx << " " << imax << "\n";  // 印出答案
    }
    return 0;
}