2020ICPC 江西省赛热身赛 E.Robot Sends Red Packets（dfs）

登录—专业IT笔试面试备考平台_牛客网

题目大意：

过年的时候，族长会给每个来拜年的人发红包。族长有一罐金币，可以用来发红包。大宗主需要把这些金币分成等量的红包，也就是宗主要给每个人等量的金币。为了让更多来拜年的人拿到红包，族长希望给尽可能多的人发红包。

族长让你帮忙，按上面说的规则发红包，这会为难你，你就让机器人帮忙。连围棋冠军都能被机器人打败，这可不是小买卖。你知道机器人怎么发红包吗？

输入描述：
第一行输入正整数T (1≤T≤29)，表示有T组测试数据。

每组测试数据输入有两行，第一行是正整数N (0 < N < 66)，代表金币数；下一行是用空格隔开的N个正整数s(每个正整数< 66)，分别代表每个金币的数量。

输出描述：
每组测试数据的输出占一行，是一个正整数，代表每个红包分成最相等的红包时的含金量。

输入描述：
第一行输入正整数T (1≤T≤29)，表示有T组测试数据。

每组测试数据输入有两行，第一行是正整数N (0 < N < 66)，代表金币数；下一行是用空格隔开的N个正整数s(每个正整数< 66)，分别代表每个金币的数量。

输出描述：
每组测试数据的输出占一行，是一个正整数，代表每个红包分成最相等的红包时的含金量。

输入

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

输出

6
5

题目大意就是要用全部的红包额划分成最小红包分给最多的人，每个单独的红包不允许拆卸，但是不同的红包之间可以相互拼凑，数据量不大，所以可以枚举+dfs查找最小红包数。

之前见过两两拼凑的，这次是可以多个进行拼凑的。

#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(leng==len) return dfs(num+1,0,1);//如果在这个构造的过程中我的一个构造长度已经达到了len，那么就说明距离梦想又近了一步

    int flag=0;
    for(int i=idx;i<=n;i++)
    {
        if(!vis[i]&&leng+a[i]<=len&&flag!=a[i])
        {
            //未使用过&&放入红包后的总数不超过大小&&不是重复的数字
            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表示能够构成的数字
            memset(vis,0,sizeof vis);//初始化全部都没有用上过
            if(dfs(1,0,1)) break;
        }
        cout<<len<<endl;
    }
    return 0;
}