首页 > 试题广场 >

小红越级（hard）

[编程题]小红越级（hard）

热度指数：4 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 本题为问题的困难版本，两题的唯一区别在于不舒适度的定义。

$\hspace{15pt}$ 给定 $n$ 首歌的两种难度版本的难度系数 $a_i, b_i$ ，小红可以任选一个版本游玩。然而，当小红的能力为 $x$ 时：
$\hspace{23pt}\bullet\,$ 如果歌的难度 $p$ 大于 $x + 1$ ，小红会获得 $p - (x + 1)$ 的不舒适度；
$\hspace{23pt}\bullet\,$ 如果歌的难度 $p$ 小于 $x - 1$ ，小红会获得 $(x - 1) - p$ 的不舒适度；
$\hspace{23pt}\bullet\,$ 如果歌的难度 $p$ 在 $[x - 1, x + 1]$ 之间，那么这首歌不会产生不舒适度。

$\hspace{15pt}$ 现在，有 $q$ 次询问，第 $i$ 次询问包含一个整数 $x_i$ ，你需要回答当小红的能力为 $x_i$ 时，以最优策略游玩这 $n$ 首歌后不舒适度的最小值。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个整数 ，表示歌曲数量、询问次数。
此后  行，第  行输入两个整数 ，表示第  首歌的两个不同难度版本的难度系数。
此后  行，第  行输入一个整数 ，表示第  次询问的能力值。

除此之外，保证单个测试文件的  之和、 之和均不超过 。

输出描述:

对于每组测试数据，在一行上输出  个整数，表示每个询问的答案。

示例1

输入

输出

0 2 4

说明

对于第一次询问，她可以每首歌都玩难度为  的版本，这样不会产生不舒适度，总不舒适度为 。

对于第二次询问，歌曲难度在  之间不会产生不舒适度：
第一首歌，游玩两个版本的不舒适度分别为 ，一定产生一点不舒适度；
第二至五首歌，游玩两个版本的不舒适度均分别为 ，显然选后者；
第六首歌，游玩两个版本的不舒适度分别为 ，显然选前者。
综上，最优策略下不舒适度为 。