扔骰子

[编程题]扔骰子

热度指数：1182 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹在和牛牛玩扔骰子，他们的游戏规则有所不同；

每个人可以扔 $n$ 次 $m$ 面骰子，来获得 $n$ 个数
得分为任意选取 $n$ 个数中的某些数求和所不能得到的最小的正整数
得分大的人获胜
例如扔骰子 $3$ 次得到了 $1$ $2$ $5$ ，那么这个人的得分是 $4$

牛妹想知道这回合她是否能赢

牛妹的n个数存在数组a中，牛牛的n个数存在数组b中

数组下标从0开始

如果牛妹能在这回合胜利则输出 $Happy$ ，否则输出 $Sad$

示例1

输入

2,4,[1,2],[1,3]

输出

"Happy"

说明

牛妹能构成   ，牛妹的得分为4
而牛牛只能构成  ，牛牛的得分为2
故牛妹胜利！

备注:

算法知识视频讲解

卖报人

/*
排序两数组，从小到大加和，比较两数组第一次出现无法覆盖的数的值即可
*/

class Solution {
public:
    string Throwdice(int n, int m, int* a, int aLen, int* b, int bLen) {
        // write code here
        long long sum1 = 0, sum2 = 0, res1 = 0, res2 = 0;
        bool flag1 = 1, flag2 = 1;
        sort(a, a + n);
        sort(b, b + n);

        for(int i = 0; i < n; i++) {
            if(flag1){
                if(a[i] > sum1 + 1)  {
                    flag1 = 0;
                    if(sum1 <= sum2) {
                        return "Sad";
                    }
                }
                else {
                    sum1 += a[i];
                }
            }

            if(flag2){
                if(b[i] > sum2 + 1)  {
                    flag2 = 0;
                    if(sum2 < sum1) {
                        return "Happy";
                    }
                }
                else {
                    sum2 += b[i];
                }
            }
            if(flag1 == 0 && flag2 == 0) {
                break;
            }
        }
        
        if(sum2 < sum1) {
            return "Happy";
        } 
        else {
            return "Sad";
        }
    }
};

发表于 2020-03-16 15:12:06 回复(0)

C/C++

nbgao

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字符串
     */
    string Throwdice(int n, int m, int* a, int aLen, int* b, int bLen) {
        long s1=0, s2=0;
        bool t1=true, t2=true;
        sort(a, a+n);
        sort(b, b+n);
        for(int i=0;i<n && (t1||t2);i++){
            if(t1){
                if(a[i]<=s1+1)
                    s1 += a[i];
                else{
                    t1 = false;
                    s1 += 1;
                }
            }
            if(t2){
                if(b[i]<=s2+1)
                    s2 += b[i];
                else{
                    t2 = false;
                    s2 += 1;
                }
            }
        }
        return (s1>s2)?"Happy":"Sad";
    }
};

编辑于 2020-08-13 01:35:48 回复(0)

科大15届软工代言人

import java.util.*;


public class Solution {
/* score2和score1的得到过程完全一致 */
    public String Throwdice (int n, int m, int[] a, int[] b) {
        //实现数组递增排序
        int[] arr1 = Arrays.stream(a).sorted().toArray();
        int score1 = 0;
        if(arr1[0] != 1) {
            score1 = 1;
        }else {
            for(int i = 1; i < n; i++) {
                if(arr1[i] > arr1[i-1] + 1)  {
                    int count = arr1[i] - arr1[i-1];
                    int j = i - 2;
                    while(j >= 0 && count > 0) {
                        if(count >= arr1[j]) {
                            count -= arr1[j];
                        }
                        j--;
                    }
                    if(count == 0)
                        continue;
                    else {
                        score1 = arr1[i];
                    }
                }
            }
        }
        int temp1 = arr1[n-1] + 1;
        while(score1 == 0) {
            temp1++;
            int count = temp1;
            int j = n-1;
            while(count > 0 && j >= 0) {
                if(count >= arr1[j]) {
                    count -= arr1[j];
                }
                j--;
            }
            if(count == 0) {
                continue;
            }else {
                score1 = temp1;
            }
        }
        
        int[] arr2 = Arrays.stream(b).sorted().toArray();
        int score2 = 0;
        if(arr2[0] != 1) {
            score2 = 1;
        }else {
            for(int i = 1; i < n; i++) {
                if(arr2[i] > arr2[i-1] + 1)  {
                    int count = arr2[i] - arr2[i-1];
                    int j = i - 2;
                    while(j >= 0 && count > 0) {
                        if(count >= arr2[j]) {
                            count -= arr2[j];
                        }
                        j--;
                    }
                    if(count == 0)
                        continue;
                    else {
                        score2 = arr2[i];
                    }
                }
            }
        }
        int temp2 = arr2[n-1] + 1;
        while(score2 == 0) {
            temp2++;
            int count = temp2;
            int j = n-1;
            while(count > 0 && j >= 0) {
                if(count >= arr2[j]) {
                    count -= arr2[j];
                }
                j--;
            }
            if(count == 0) {
                continue;
            }else {
                score2 = temp2;
            }
        }
        if(score1 > score2) {
            return "Happy";
        }else {
            return "Sad";
        }
    }
}

发表于 2021-07-09 21:33:45 回复(0)