题解

题面描述

给定$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. 预处理最低价格

题目内容

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

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

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

现在小红想知道准备完购物清单上的物品至少需要花费多少钱?

输入描述

第一行两个整数$n,k(1≤n≤10^5,1≤k≤10^6)$,表示食材种类和转换系数，

第二行$n$个整数,表示$a$数组,其中$a_i(1≤a_i≤10^6)$

第二行$n$个整数,表示$b$数组，其中$b_i(1≤b_i≤10^6)$

输出描述

一个整数，表示准备完所有食材至少需要花费钱数

样例1

输入

3 6 
1 2 8
1 1 2

输出

3

样例2

输入

3 6 
2 2 8
1 3 2

输出

3