POJ 3782 Equal Sum Partitions：模擬枚舉最小分割和

題目大意

給定長度 n 的正整數序列，將其分割為若干連續段，使每段和相等。求可能的最小段和。

直接模擬枚舉

總和 S。枚舉目標段和 target = 1..S：

• 掃描序列累加，若累加和 == target 歸零繼續；若 > target 失敗；掃描結束若累加和 != 0 失敗。
• 第一個成功的 target 即答案（因從小枚舉）。

n ≤ 10000, S ≤ 10⁷，但測試數據弱，O(S) 枚舉 + O(n) 驗證通常能過。實際可優化：只枚舉 S 的約數作為 target。

C++ 代碼

#include 
using namespace std;
int a[10010];

bool check(int n, int target) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
        if (sum == target) sum = 0;
        else if (sum > target) return false;
    }
    return sum == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int tc, n; cin >> tc >> n;
        int S = 0;
        for (int i = 0; i < n; ++i) { cin >> a[i]; S += a[i]; }
        int ans = S;
        for (int t = 1; t <= S; ++t) {
            if (S % t != 0) continue; // 僅枚舉約數
            if (check(n, t)) { ans = t; break; }
        }
        cout << tc << ' ' << ans << '\n';
    }
    return 0;
}

優化：僅枚舉約數

若總和 S，段和 target 必須整除 S。先求出 S 的所有約數，排序後從小驗證，複雜度降為 O(√S + d(S)·n)，極快。

總結

POJ 3782 是「枚舉驗證」類水題。關鍵優化：段和必須是總和的約數。掌握 for (int t=1; t*t<=S; ++t) if (S%t==0) ... 約數枚舉模板，配合線性驗證，輕鬆解決同類分割問題。