2020icpc Jiangxi warm up e.robot sends red packets (DFS)

Sign in — major IT Written interview preparation platform _ Cattle from

The main idea of the topic ：

New year's Day , The patriarch will send red envelopes to everyone who comes to pay New Year's greetings . The patriarch has a pot of gold coins , It can be used to send red envelopes . The great patriarch needs to divide these gold coins into equal red envelopes , That is, Zong mainly gives everyone the same amount of gold coins . In order to let more people get red envelopes , The patriarch hopes to give red envelopes to as many people as possible .

The patriarch asked you to help , Send red envelopes according to the above rules , This will embarrass you , You just let the robot help . Even the go champion can be defeated by robots , This is not a small business . Do you know how robots send red envelopes ？

Input description ：
Enter a positive integer in the first line T (1≤T≤29), Express T Group test data .

Each set of test data input has two lines , The first line is a positive integer N (0 < N < 66), Represents the number of gold coins ; The next line is separated by spaces N A positive integer s( Every positive integer < 66), Each represents the number of gold coins .

Output description ：
The output of each group of test data occupies one line , Is a positive integer , Represents the gold content when each red packet is divided into the most equal red packets .

Input description ：
Enter a positive integer in the first line T (1≤T≤29), Express T Group test data .

Each set of test data input has two lines , The first line is a positive integer N (0 < N < 66), Represents the number of gold coins ; The next line is separated by spaces N A positive integer s( Every positive integer < 66), Each represents the number of gold coins .

Output description ：
The output of each group of test data occupies one line , Is a positive integer , Represents the gold content when each red packet is divided into the most equal red packets .

Input

2
6
5 2 1 5 1 4
4
1 2 3 4

Output

6
5

The main idea of the topic is to divide the total amount of red envelopes into the smallest red envelopes and give them to the most people , Each individual red envelope is not allowed to be disassembled , But different red envelopes can be pieced together , Not a lot of data , So you can enumerate +dfs Find the minimum number of red packets .

I've seen two pieces before , This time it can be pieced together more .

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200200;
int a[N],b[N],vis[N];
int n,sum,maxn,len,cnt;
bool dfs(int num,int leng,int idx)
{
    if(num>cnt) return true;// If the number has reached the standard , Then it can constitute this 
    if(leng==len) return dfs(num+1,0,1);// If the length of one of my constructs has reached len, Then it means that we are one step closer to our dream 

    int flag=0;
    for(int i=idx;i<=n;i++)
    {
        if(!vis[i]&&leng+a[i]<=len&&flag!=a[i])
        {
            // Not used && The total number of red envelopes should not exceed the size && Not duplicate numbers 
            vis[i]=1;
            if(dfs(num,leng+a[i],i+1)) return true;

            flag=a[i];

            vis[i]=0;
            if(leng==0||leng+a[i]==len) return false;
        }
    }
    return false;
}
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        sum=0,maxn=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum+=a[i];
            maxn=max(maxn,a[i]);
        }
        sort(a+1,a+1+n);
        reverse(a+1,a+1+n);
        //for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl;
        for(len=maxn;len<=sum;len++)
        {
            if(sum%len) continue;
            cnt=sum/len;//len Represents a number that can be formed 
            memset(vis,0,sizeof vis);// Initialization has never been used 
            if(dfs(1,0,1)) break;
        }
        cout<<len<<endl;
    }
    return 0;
}