第五章 二叉堆
P2168 [NOI2015] 荷马史诗
P2827 [NOIP2016 提高组] 蚯蚓
找最长的蚯蚓只需要直到相对大小,其余蚯蚓长度 \(+q\) 等价于新产生的两条蚯蚓长度 \(-q\)
新产生的第一/二条蚯蚓长度分别单调,可以用队列代替堆
时间复杂度 \(O(n\log n+m)\)
P1801 黑匣子
对顶堆
P1631 序列合并
\(a,b\) 不降所以 \(a[i]+b[j]\) 一定比 \(a[i+1]+b[j],a[i]+b[j+1]\) 优
用堆维护可能成为答案的数对,取出 \((i,j)\) 后放入 \((i+1,j),(i,j+1)\)
P4053 [JSOI2007] 建筑抢修
返回贪心
标签:进阶,VO.7,深入浅出,进阶篇,长度,蚯蚓 From: https://www.cnblogs.com/ft61/p/17720887.html