b_lc_心算挑战(排序+贪心)

选手从 N 张卡牌中选出 cnt 张卡牌,若这 cnt 张卡牌数字总和为偶数,则选手成绩「有效」且得分为 cnt 张卡牌数字总和。 请帮参赛选手计算最大的有效得分 n,cnt<1e5

思路:贪心就是指尽可能拿大的数;奇数肯定只能不拿/拿两个,偶数随便拿大的就行

class Solution {
public:
    int maxmiumScore(vector<int>& A, int cnt) {
        vector<int> odd = {0}, even = {0};

        for (const auto &item : A) {
            if (item % 2 == 0) {
                even.push_back(item);
            } else {
                odd.push_back(item);
            }
        }
        sort(even.begin() + 1, even.end(), greater<int>());
        sort(odd.begin() + 1, odd.end(), greater<int>());

        for (int i = 1; i < odd.size(); ++i) {
            odd[i] += odd[i-1];
        }
        for (int i = 1; i < even.size(); ++i) {
            even[i] += even[i-1];
        }
        int ans = 0;

        for (int i = 0; i <= cnt; i += 2) {
            int oddSize = i, evenSize = cnt - i;
            if (oddSize >= odd.size() || evenSize >= even.size()) {
                continue;
            }
            ans = max(ans, odd[oddSize] + even[evenSize]);
        }
        return ans;
    }
};
上一篇:LeetCode练习——链表(奇偶链表)


下一篇:Believing Process 力扣328.奇偶链表