题解 | #扔骰子#

一.题目描述
NC520扔骰子
牛妹在和牛牛玩扔骰子，他们的游戏规则有所不同；
每个人可以扔n次m面骰子，来获得n个数，得分为任意选取n个数中的某些数求和所不能得到的最小的正整数
得分大的人获胜
例如：扔骰子3次得到了1,2,5，那么这个人的得分是4。
牛妹想知道这回合她是否能赢？牛妹的n个数存在数组a中，牛牛的n个数存在数组b中，数组下标从0开始，如果牛妹能在这回合胜利则输出Happy，否则输出Sad。
二.算法(排序)
图片说明
题意可以转化为我们要找到一个最大的sum,使得1到sum都能被构造出来，那么答案就是sum+1。首先需要我们先把数字排个序，使集合是从小到大排序的。我们用a1到an来表示1到sum，如果此时我们新加入一个数ans，如果ans能加入集合需要满足ans<=sum+1，否则就不能加入。那么做法就很明显了，我们只需要先把数从小到大排序，维护这个集合，直到新加入的数ans>sum+1，答案就是sum+1。下面是完整代码：

class Solution {
public:
    //得分判断
    long long check(int n,vector<int> a){
        sort(a.begin(),a.end());
        long long sum=0;
        for(int i=0;i<n;i++){
            if(a[i]>sum+1) break;
            sum+=a[i];
        }
        //返回sum+1
        return sum+1;
    }
    string Throwdice(int n, int m, vector<int>& a, vector<int>& b) {
        if(check(n,a)>check(n,b)) return "Happy";
        else return "Sad";
    }
};

时间复杂度： $O(nlogn)$ ,只需要对数组进行一次排序
空间复杂度： $O(1)$ ,不需要额外的空间存储
优缺点：实现简单，便于实现
三.算法(java的实现)
思路和方法二相似，下面是完整代码：

import java.util.*;
public class Solution {
    private int check(int[] nums,int n){
        //对数组进行排序
        Arrays.sort(nums);
        int sum=0;
        for(int i=0;i<n;i++){
            if(nums[i]<=sum+1){
               sum+=nums[i];
            } else {
                break;
            }

        }
        return sum+1;
    }
    public String Throwdice (int n, int m, int[] a, int[] b) {
        //判断牛牛和牛妹谁的得分高
        if(check(a,n)>check(b,n)){
            return "Happy";
        } else {
            return "Sad";
        }
    }
}

时间复杂度： $O(nlogn)$ ,只需要对数组进行一次排序
空间复杂度： $O(1)$ ,不需要额外的空间存储
优缺点：思路简单，但是实现起来相比算法二很复杂。