题目描述

blablabla

样例

自己复习用，非题解，请谅解！

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 70;
int n, sum, m;
int a[N];
bool st[N];

bool dfs(int u, int cur, int start)
{
    if (u * m == sum) return true;
    if (cur == m) return dfs(u + 1, 0, 0);

    for (int i = start; i < n; i ++)
    {
        if (st[i]) continue;
        int l = a[i];
        if (l + cur <= m)
        {
            st[i] = true;
            if (dfs(u, cur + l, i + 1)) return true;
            st[i] = false;
        }

        if (!cur || cur + l == m) return false;
        int j = i + 1;
        while (j < n && a[j] == l) j ++;
        i = j - 1;
    }
    return false;
}

int main()
{
    while (cin >> n, n)
    {
        sum = m = 0;
        memset(a, 0, sizeof a);
        for (int i = 0; i < n; i ++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
            m = max(m, a[i]);
        }
        sort(a, a + n, greater<int>());    
        memset(st, 0, sizeof st);
        while (true)
        {
            if (sum % m == 0 && dfs(0, 0, 0))
            {
                cout << m << endl;
                break;
            }
            else m ++;
        }
    }


    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla