【Fifty Project - D29】

今日完成记录

Leetcode

堆题单

多次求和构造目的数组：给一个目标数组target，现在有一个初始数组全是1，你可以进行任意次如下操作：选择任意下标，将对应的数变为当前数组的和。问最终能否将初始数组变为目标数组。
思路：一开始想了个简单暴力思路，因为每次操作后的数组和是严格递增的，所以可见一定是先达成目标数组中的小的数值，再完成大的数值。排序目标数组，然后从最小开始往最大遍历，对该数进行上述操作，每次操作如果都对当前数字操作，那么每次这个数字会增加sum - x，这是一个固定的值，其实就是数组除去当前数字的和，其他数不变的情况下必然是不变的，因此每次只需要判断当前数和目标数的差是否为sum-x的整数倍即可，不是则失败。但这个思路需要证明一直对当前数字进行操作是一个正确方案。好像证明不出来，为了达到目标数，是有可能先操作当前数，又操作其他数，再回头操作这个数达到目标的。
tip1：考虑到当前数组的和是严格递增的，那么目标数组中最大的那个数，必然是最后一次操作得到（其实这个点我也想到了，只是思维没有反着想一下），因此可以反着思考，最后一次操作的时候，其他数肯定已经是目标数组了，也就是我们可以得到最后一次操作之前这个数字应该是多少。
例如，对于数组 [2，3，10，16]， 最后一次操作前最后一位是x，即 [2，3，10，x]。那么最后一次操作就是x + 2 + 3 + 10 = x + 15 = 16，可知最后一次操作之前这个数字是16-15=1.也就是说数组是[2, 3, 8, 1]. 发现这个数字是1，也就是说明它可以从初始为1的数经过操作得到目标数16。
tip2：将最大的数减去数组的其余部分（就是上面说的逆操作），然后将新的元素放到数组中，重复直到整个数组都变成1.
这个tip的意思就是向刚刚说的检查最大的数能否通过逆操作变为1，如果不能就返回失败，能则继续判断剩下部分的最大值能否通过逆操作变为1，一直执行直到所有数都变为1（最大值变为1）维护最大值的过程用堆实现。

最大子序列的分数：给两个数组nums1和nums2，长度都是n，求一个长度为k的子序列的最大可能得分。得分规则：长度为k的子序列idxs是指由1-n中取得k个数字，下标对应nums1中的数字求和乘以下标对应nums2中的最小值，如下：
$$score=\sum _{i=0}^{k}nums1[idxs[i]]\ast min(nums2[idx[i]])$$
思路：观察数据规模发现n是1e5，k也是1e5，因此解法应该是nlogn，感觉是先排序，然后遍历数组，并且用logn复杂度的操作维护最小值或者最大和（堆）。顺着这个思路想，最后对nums2降序排，这样遍历到哪都能直接知道当前备选集的最小值是谁（当前入队则为最小值），同时对应的nums1，需要维护备选集中的最大sum，也就是topk之和（最小堆可以实现，每个入备选集都加到sum，如果备选集数量大于k，则从最小堆弹出并且减去sum，这样备选集永远有着k个最大的数）遍历结束则可得到解决方案。

健身

今天休息日，连续的训练并没有带来太大的肌肉疼痛感，我知道自己应该是因为疲劳导致每次训练的精神不集中以至于无法冲刺更大的重量造成更大的肌肉撕裂。所以今天简单地练了几组手臂，希望自己早点恢复过来吧。

今天还开始了消息队列的学习，早上简单看了二十分钟的课，一直想开始却一直因为各种事情以及自己的惰性搁置，希望能早点敦促自己完成这部分的学习吧