问个DP沙雕板子题,除了楼主都会

回复帖子

@天泽龟 2019-02-12 09:49 回复

给定一个初始数列,数列内部元素互相加(可以自己加自己)得到新的元素加入数列,问排序后的第n项是多少?

有点像NOIP2018D1T2,N<100000,a[i]<INT范围。

应该是裸的DP不会,wcsl

@杜岱玮 2019-02-12 10:07 回复

@天泽龟 两个heap,一个大根堆,一个小根堆,维护相同的集合。一开始就是初始序列。之后循环以下操作直到集合不发生改变:1.找到两个最小元素相加得到新元素加入集合2.弹出最大的元素直到集合大小小于N

@杜岱玮 2019-02-12 10:08 回复

需要一个堆删除的小技巧,要不写个BBST也可以。最后最大元素即为答案

@杜岱玮 2019-02-12 10:13 回复

明白了,是初始化的时候就要考虑自己加自己

@杜岱玮 2019-02-12 10:18 回复

三楼的算法好像只是没考虑两个相同元素相加的情况,把这个特判一下就好了