acwing 167. 木棒

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

注意: 数据中可能包含长度大于50的木棒，请在处理时忽略这些木棒。

输入格式

输入包含多组数据，每组数据包括两行。

第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式

为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

 

我的TLE代码  改成c的数组操作才通过

// 11111111.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include <iostream>

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int n, m;

const int N = 65;
int arr[N];
int realCount;
int maxLen = 0;
int sum = 0;
int len;
int tryCnt;
int vis[N];

int cmp(int a, int b)//从大到小排序
{
    return a > b;
}

bool dfs(int segCount, int segLen, int lastSelect)
{
    bool bret = false;
    if (segCount == tryCnt) return true;
    if (segLen == len) return dfs(segCount + 1, 0, 0);
    int fail = 0;
    for (int i = lastSelect; i < realCount; i++) {

        if (!vis[i] && arr[i] != fail && segLen + arr[i] <= len)//没有被访问,不是上一次失败的值,长度满足在len以内
        {
            vis[i] = 1;
            if (dfs(segCount, segLen + arr[i], i + 1))//开始下一次dfs
                return true;
            fail = arr[i];//失败了,当然要记录了
            vis[i] = 0;//这个数没有选择
            if (segLen == 0 || segLen + arr[i] == len)//如果cab为0,或者相加正好是len,但是失败了,那么一定是失败了.
                return false;
        }
    }

    return false;
}


int main()
{
    ios::sync_with_stdio(false);

    while (cin >> n && (n != 0)) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            if (tmp > 50)
                continue;
            arr[realCount] = tmp;
            maxLen = max(maxLen, arr[realCount]);
            sum += arr[realCount++];
        }
        sort(arr, arr + realCount,cmp);


        for (len = maxLen; len <= sum; len++)//优化
        {
            if (sum%len)//如果除不尽,肯定不满足题意
                continue;
            tryCnt = sum / len;//计算出cnt多少段
            //cout << "sum = " << sum << ".  len = " << len << endl;
            memset(vis, 0, sizeof(vis));//初始化
            if (dfs(0, 0, 0))//搜索成功,最小值就是它
                break;
        }
        cout << len << endl;
    }


    return 0;
}