题目内容

小红正在准备烹饪需要的食材，购物清单上一共列举了$n$条需要购买的食材信息。

每条信息为$a_i,b_i$。表示需要购买一个类型为$a_i$，价格为$b_i$的食材。

两种物品若满足$|a_i-a_j|≤k$,那对于$a_i$可以选择购买$a_j$替换，同理$a_j$也可以购买$a_i$来替换。

题解

题面描述

给定$n$条购物清单，每条信息为$a_i,b_i$，表示需要购买一种类型为$a_i$、价格为$b_i$的食材。若两种食材满足$|a_i-a_j| \le k$，则可以相互替换。即对于需要$a_i$的食材，可以选择购买$a_j$来替换（前提是$|a_i-a_j|\le k$）。问：购买所有物品至少需要花费多少钱？

思路

题目的核心在于先预处理所有食材类型的最低价格，再利用线段树对每个需求对应的区间$[a_i-k, a_i+k]$内进行快速区间最小值查询，从而在$O(n\log M)$的时间复杂度内求出每个需求的最小购买价格并累加得到总花费。

1. 预处理最低价格