LCP 40. 心算挑战

「力扣挑战赛」心算项目的挑战比赛中，要求选手从 N 张卡牌中选出 cnt 张卡牌，若这 cnt 张卡牌数字总和为偶数，则选手成绩「有效」且得分为 cnt 张卡牌数字总和。
给定数组 cards 和 cnt，其中 cards[i] 表示第 i 张卡牌上的数字。 请帮参赛选手计算最大的有效得分。若不存在获取有效得分的卡牌方案，则返回 0。

示例 1：

输入：cards = [1,2,8,9], cnt = 3

输出：18

解释：选择数字为 1、8、9 的这三张卡牌，此时可获得最大的有效得分 1+8+9=18。

示例 2：

输入：cards = [3,3,1], cnt = 1

输出：0

解释：不存在获取有效得分的卡牌方案。

提示：

1 <= cnt <= cards.length <= 10^5
1 <= cards[i] <= 1000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/uOAnQW
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

根据题意，假如cnt为奇数，那么必然需要至少一个偶数；且奇数一定是成对的。 因为奇数一定要成对，那么我们在选择卡牌时可以每次选择2个，这两个要么是奇数，要么是偶数。 选择时，需要分如下的情况：

• 假如cnt是奇数，我们先选择一个最大的偶数，从而将cnt变为偶数。
• 假如奇数和偶数剩余的数量都大于等于2个，那么我们需要比较下最大和次大的偶数之和与最大与次大的奇数之和，这两个和哪个大，我们选择较大的一组；
• 假如奇数剩余数量不到2个并且偶数剩余数量大于等于2个，因为cnt现在一定是偶数，而奇数一定不可以选择了，故选择最大和次大的两个偶数。
• 假如偶数剩余数量不到2个并且奇数剩余数量大于等于2个，因为cnt现在一定是偶数，而偶数数量不到2个，也就是最多一个，假如选择了偶数，那么偶数就没有了，剩下的只能选择奇数，会导致最终选择失败。
• 其他情况表示无法满足条件，选择失败。比如当cnt>0时但最多有一个奇数和最多有一个偶数。

 public int maxmiumScore(int[] cards, int cnt) {
        Arrays.sort(cards);
        int[] odds = Arrays.stream(cards).filter(k -> k % 2 == 1).toArray();
        int[] evens = Arrays.stream(cards).filter(k -> k % 2 == 0).toArray();
        int oddIdx = odds.length - 1;
        int evenIdx = evens.length - 1;
        int sum = 0;
        if (cnt % 2 == 1) {
            if (evenIdx >= 0) {
                sum += evens[evenIdx--];
            }else{
                //如果是奇数，并且没有偶数了，说明不能组成
                return 0;
            }
            cnt--;
        }
        while (cnt > 0) {
                //如果是偶数

                if (evenIdx >= 1 && oddIdx >= 1) {
                    //如果奇数和偶数剩余数量都大于等于2
                    int oddSum = odds[oddIdx] + odds[oddIdx - 1];
                    int evenSum = evens[evenIdx] + evens[evenIdx - 1];
                    if (oddSum >= evenSum) {
                        sum += oddSum;
                        oddIdx -= 2;
                    }else{
                        sum += evenSum;
                        evenIdx -= 2;
                    }
                } else if (oddIdx >= 1) {
                    int oddSum = odds[oddIdx] + odds[oddIdx - 1];
                    sum += oddSum;
                    oddIdx -= 2;
                } else if (evenIdx >= 1) {
                    int evenSum = evens[evenIdx] + evens[evenIdx - 1];
                    sum += evenSum;
                    evenIdx -= 2;
                }else {
                    return 0;
                }
                cnt -= 2;
        }
        return sum;
    }