#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}

int last_pos(int flag[], int pos)
{
    for(int i = 0; i < pos; i ++)
        if(flag[i] == 0)
            return i-1;
}
int main()
{
    int a[65];
    int sticks[65];
    int flag[65];
    int n;
    while(cin >> n && n !=0)
    {
        int sum = 0;
        memset(a,0,sizeof(a));
        for(int i = 0; i < n; ++i)
        {
            cin >> a[i];
            sum += a[i];
        }
        qsort(a,n,sizeof(int),cmp);
        for(int length = a[n-1]; length <= sum; length++)
        {
            if(sum % length != 0)
            {
                continue;
            }
            int count = 0;
            int pos = -1;
            memset(flag,0,sizeof(flag));
            for(int i = (n-1); i >= 0; i--)
            {
                int k = 0;
                if(flag[i] == 1)
                    continue;
                memset(sticks,-1,sizeof(sticks));
                sticks[k++] = i;
                flag[i] = 1;
                if(a[i] == length)
                {
                    count ++;
                    continue;
                }
                int tmp = a[i];
                for(int j = i -1; j >= 0; j--)
                {
                    if(flag[j] == 1)
                    {
                        if(j > (pos+1))
                            continue;
                    }
                    else if(tmp + a[j] > length)
                    {
                        if(j > (pos+1))
                            continue;
                    }
                    else if(tmp + a[j] < length)
                    {
                        sticks[k++] = j;
                        tmp += a[j];
                    }
                    else if(tmp + a[j] == length)
                    {
                        sticks[k++] = j;
                        for(int m = k - 1; m >= 0; m--)
                        {
                            flag[sticks[m]] = 1;
                        }
                        pos = last_pos(flag, 65);
                        count ++;
                        break;
                    }
                    if(j == (pos+1))
                    {
                        int p = 0;
                        int esc = 1;
                        if(sticks[k-1] == j)
                        {
                            tmp -= a[sticks[k-1]];
                            sticks[k-1] = -1;
                            k--;
                        }
                        if(k <= 1)
                        {
                            break;
                        }
                        tmp -= a[sticks[k-1]];
                        while(a[sticks[k-1]-p] == a[sticks[k-1]])
                        {
                            p++;
                            if(sticks[k-1]-p <= pos)
                            {
                                tmp -= a[sticks[k-1]];
                                k--;
                                if(k-1 < 1)
                                {
                                    esc = 0;
                                    break;
                                }
                                p = 0;
                                sticks[k-1] = -1;
                            }
                        }
                        sticks[k-1] = -1;
                        if(esc == 0)
                        {
                            break;
                        }
                        j = sticks[k-1]-p;
                        k--;
                    }
                }
                if(count == sum/length-1)
                {
                    break;
                }
            }
            if(count == sum/length-1 || count == sum/length)
            {
                cout << length << endl;
                break;
            }
        }
    }
    return 0;
}

• Re:一直WA，测试数据都正确 (100) xqj90 2012-03-22 22:00:55