难度: Easy
运行时间: 276 ms
内存: 26.3 MB
class Solution:
def maxmiumScore(self, cards: List[int], cnt: int) -> int:
a, b, c,d = 1001, 1001, 0, 0
cards = sorted(cards, reverse = True)
pcards, bcards, rcards = cards[:cnt], cards[cnt:], sorted(cards[:cnt])
scards = sum(pcards)
if scards % 2 and not bcards:
return 0
for i in bcards:
if i % 2 == 0:
c = max(i, c)
else:
d = max(i, d)
if c and d:
break
for j in rcards:
if j % 2 == 0:
a = min(j, a)
else:
b = min(j, b)
if a != 1001 and b != 1001:
break
if scards % 2:
return max(scards - a + d, scards - b + c)
else:
return sum(pcards)
这道题的思路是首先对卡牌进行降序排序，然后选择前cnt张卡牌作为初始方案。如果这些卡牌的总和是偶数，那么这就是最大有效得分。如果总和是奇数，需要找到一种方式将其转换为偶数。这可以通过替换一张卡片来实现，具体方法是：在已选择的卡牌中找到最小的偶数卡和最小的奇数卡，在未选择的卡牌中找到最大的偶数卡和最大的奇数卡。然后比较替换这些卡牌后的总和，选择一个更大的有效得分。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def maxmiumScore(self, cards: List[int], cnt: int) -> int:
a, b, c, d = 1001, 1001, 0, 0 # 初始化最小的偶数卡a、最小的奇数卡b、最大的偶数卡c和最大的奇数卡d
cards = sorted(cards, reverse=True) # 降序排序卡牌
pcards, bcards, rcards = cards[:cnt], cards[cnt:], sorted(cards[:cnt]) # 分别获取已选择的卡牌、未选择的卡牌和已选择卡牌的升序列表
scards = sum(pcards) # 计算已选择卡牌的总和
if scards % 2 and not bcards: # 如果总和为奇数且没有未选择的卡牌，则无法获得有效得分
return 0
for i in bcards: # 遍历未选择的卡牌
if i % 2 == 0:
c = max(i, c) # 更新最大的偶数卡
else:
d = max(i, d) # 更新最大的奇数卡
if c and d:
break
for j in rcards: # 遍历已选择的卡牌的升序列表
if j % 2 == 0:
a = min(j, a) # 更新最小的偶数卡
else:
b = min(j, b) # 更新最小的奇数卡
if a != 1001 and b != 1001:
break
if scards % 2: # 如果总和为奇数，则通过替换卡牌使其变为偶数
return max(scards - a + d, scards - b + c)
else:
return sum(pcards) # 如果总和已经是偶数，则直接返回
降序排序卡牌是为了确保在选择前cnt张卡牌时，我们能够拿到最大可能的数值总和。这种策略的目的是最大化初始选择的卡牌的分数，因为较大的数值卡牌通常对总得分的贡献更高。选择较大的数值可以最大化初始的总和，从而为后续可能的调整（例如通过替换卡牌来调整总和的奇偶性）提供一个较高的起点，增加达到或超过其他方案的可能性。
如果所有卡牌都已被选择，且没有剩余的卡牌可以用于替换，那么已选择的卡牌总和若为奇数，则无法通过任何替换来改变其奇偶性。题目的要求是找到最大有效得分，而有效得分必须是偶数。由于没有额外的卡牌可以用于调整总和的奇偶性，因此这种情况下无法达成有效得分，只能返回得分为0。
选择最小的偶数卡和最小的奇数卡进行替换的逻辑是基于最小化损失的原则。在需要将总和从奇数转变为偶数的情况下，替换最小的偶数卡和最小的奇数卡可以尽量减少对已有总得分的负面影响。理论上，如果有更大的偶数卡或奇数卡可用于替换，那么可能会有更优的替换策略，从而实现更高的得分。但这需要在保持总和为偶数的前提下，对所有可能的替换组合进行详细的评估，以找出能够产生最高总得分的替换方案。