ZeroJudge 解題筆記：c134. 00668 - Parliament

作者：王一哲
日期：2026年3月25日


ZeroJudge 題目連結：c134. 00668 - Parliament

解題想法

這題要將某個正整數 n，分拆成任意個不重複的正整數，使分拆後的正整數乘積最大。因為拆成 1 不會使乘積變大，至少從 2 開始分拆，盡量拆成越多個數字越好。如果 $n \leq 4$ 分拆後的正整數乘積不會大於 $n$，因此題目的測資 $\geq 5$ 。分拆時從 $i=2$ 開始測試，每次分拆後將 $n-i$，直到 $n < i$ 為止，如果最後 $n > 0$ ，再將分拆出來最大的 $n$ 個數都加 1。 注意：此題的答案只要輸出分拆後的正整數，不需要輸出個數。題目敘述與測資的要求不合。

Python 程式碼

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

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    T = int(data[0])
    ptr = 1
    while ptr < len(data):
        n = int(data[ptr])
        ptr += 1
        if result:  # 不是第一組測資，先換行
            result.append("\n")
        if n <= 4:  # 特例，小於等於 4，不能分拆
            result.append(f"{n:d}\n")
        else:
            i = 2  # 從 2 開始測試
            ans = []  # 分拆的數字
            while n >= i:  # 如果 n 還能分拆
                ans.append(i)  # i 加入 anss
                n -= i  # n 減去 i
                i += 1  # i 加 1
            for j in range(len(ans)-1, len(ans)-n-1, -1):  # 最後 n 個數加 1
                ans[j] += 1
            res = " ".join(map(str, ans))
            result.append(f"{res}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

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

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

int main() {
    int t; scanf("%d", &t);
    for(int i=0, n; i<t; i++) {
        scanf("%d", &n);
        vector<int> nums;
        int j=2;
        while(n >= j) {
            nums.push_back(j);
            n -= j;
            j++;
        }
        int m = (int)nums.size();  // nums 的長度
        int idx = m-1;  // 索引值從最後一項開始
        for(int k=0; k<n; k++) {
            nums[idx]++;
            idx = (idx - 1 + m) % m;
        }
        if (i > 0) puts("");
        for(int k=0; k<(int)nums.size()-1; k++) printf("%d ", nums[k]);
        printf("%d\n", nums.back());
    }
    return 0;
}