选手从 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;
}
};