第二题
题目大意
题目给出一个长度为nnn的序列a,aia_iai 分为两块部分,为count,valcount,valcount,val 数量与数值
现在你可以使用aia_iai 当中的valvalval去搭建一个积木塔的数字序列。积木塔的数字序列的要求为
我们设定积木塔的序列名称为bbb,则需要
bi−bi−1=kb_{i} - b_{i-1} = kbi −bi−1 =k ,bib_ibi 与bi−1b_{i-1}bi−1 才可以连接在一起。
现在你可以使用序列aaa去组件mmm个序列bbb,每个aia_iai 的val可以背使用的次数为count,求解所有的序列b总计最多使用多少数字。
根据贪心原理,我们可以很快得知,如果你想要让一个序列bbb尽可能的长,你就需要将较小的数字放置于上方,较大的放置于下方,尽可能按照这样去排放,才可以让其最长。
1. Sort对于a数组按照val的数值进行从小到大排序。
2. 使用for循环枚举m个序列b
3. 再放一个for循环,寻找组成b的合法元素aia_iai
1. 循环遍历m组积木塔 O(m)
2. 循环寻找n个数字查看是否可以添加到积木塔当中。 O(n)
我们添加数字到积木塔当中时,是一个个添加进去的,也就是说非常的低效,有没有一种办法,在遍历当前第i个数字的时候,我们就可以知道当前这个数字能放到多少个积木塔当中呢?
假如说,存在一种方法,使得我们在遍历n个数字的时候,每遍历一个数字,就可以将其分配到m个积木塔当中,并且不需要循环来匹配,那么时间复杂度就可以降至O(n)。
我们思考一件事情,积木塔的长度没有限制,也就是说,我们可以任意的往积木塔当中添加符合条件的数字。
假设已经按照从小到大的顺序排列好了数字,那么我们从数字当中拿取拼接到积木塔当中的遍历顺序一定是从左往右。
假如说,当前拿取的数字是a[id].value,对于所有与他差值为k的数字都可以接在后面。那么我们是不是可以认为所有差值为k的数字总数可以直接累加进答案里?
假设a[id].value = 1 ,现在有其他value与count分别为 [2,5][3,6] ,且k=1.
那我们是不是可以直接认为答案answer 可以加 5和6?
不可以,原因为: 以1作为上一个元素的积木塔可能没那么多。
所以可以累加的大小为 min(m,5) 或min(m,6)或min(m,5+6)。
又或者1的数量只有3个,那么只能接3个数字在后, 优先选择较小的。
但是在这里,我们可以发现一个关键性的问题,我们没必要一个个匹配过去,我们完全可以把一个aia_iai 的count个数字直接平铺在某一层当中。然后在到其他的数字当中寻找可以衔接在下一层的其他数字继续平铺。
那么我们在这里设定上一个数字的编号为 id 开始书写。