扔骰子题解

做法1：AC
题意可以转化为我们要找到一个最大的,使得都能被构造出来，那么答案就是。很明显我们为了维护这个集合，需要先把数字排个序，因为集合是从小往大扩充的。考虑我们已经可以用的数表示了的数，此时我们新加入一个数，能加入集合需要满足如下特征：
原因是如果，那么将缺失。
那么做法就很明显了，我们只需要先把数从小到大排序，维护这个集合，直到新加入的数，答案就是。
总的时间复杂度，空间复杂度

class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param aLen int a数组长度
     * @param b int整型一维数组 b
     * @param bLen int b数组长度
     * @return string字符串
     */
    long long solve(int n,int *a) {
        sort(a,a+n);
        long long sum = 0;
        for(int i=0;i<n;i++) {
            if(a[i]>sum+1) break;
            sum += a[i];
        }
        return sum+1;
    }
    string Throwdice(int n, int m, int* a, int aLen, int* b, int bLen) {
        // write code here
        if(solve(n,a)>solve(n,b)) return "Happy";
        else return "Sad";
    }
};

做法2：（TLE）
和上述一样先转化为我们要找到一个最大的,使得都能被构造出来，那么答案就是。为了找到这个我们通过dfs枚举每一个数取或不取。这样的数会有个，我们将其排序，然后找到X就行。时间复杂度，空间复杂度。

class Solution {
public:
    /**
     * 
     * @param n int整型 n
     * @param m int整型 m
     * @param a int整型一维数组 a
     * @param aLen int a数组长度
     * @param b int整型一维数组 b
     * @param bLen int b数组长度
     * @return string字符串
     */
    typedef long long ll;
    ll sum, a[100005],b[100005],ch[5000005],tt;
    void dfs(int x,int limit,ll sum,int *a) {
        if(x==limit) {
            if(sum!=0) ch[tt++]=sum;
            return ;
        }
        dfs(x+1,limit,sum+a[x],a);
        dfs(x+1,limit,sum,a);
    }
    ll solve(int *a,int n) {
        tt=0;
        dfs(0,n,0,a);
        sort(ch,ch+tt);
        if(ch[0]!=1) return 1;
        else  {
            int pos=1;
            while(1) {
                if(ch[pos]-ch[pos-1]!=1&&ch[pos]-ch[pos-1]!=0) return ch[pos-1]+1;
                else pos++;
            }
        }
    }
    string Throwdice(int n, int m, int* a, int aLen, int* b, int bLen) {
        // write code here
        if(solve(a,n)>solve(b,n)) {
            return "Happy";
        }else return "Sad";
    }
};