每日一题:共鸣问题
题意
现在有 n 个音符和 m 对共鸣关系,编号为 1−n,每个音符自己有一个奏响时的优美程度,共鸣关系 (x,y,z) 表示音符 x 和 y 同时奏响的额外优美程度是 z,同时不奏响则为 −z,其他情况为 0,求最大优美程度。(n,m∈[1,1e5])
思路
对于一对共鸣关系而言,在不选的情况下收益为 −z,则选择一个的话,收益为 −z+z=0,都选择的话为 −z+2z=z。因此可以预先把每对关系的两个数都加上 z,刚开始我们是不选任何有联系的音符的,因此初值为 −z,那么选择一个数就会加上 z,选择两个就会加上 2z,满足了之前所讨论的关系。答案初始化为所有关系都不选的情况,即 −sum(z),然后只要贪心的选择对答案有正贡献的值就行了。
Code
1 | class Solution { |