Skip to content

1004: Pio's Sequence

题目

题目描述

Pio 是一名药水制作师,制作药水需要许多种类的素材。有一天,粗心的 Tia 不小心把做好的药水全部打翻在素材上了,之前做好的药水和库存的素材全部没法用了!于是接下来的 $n$ 天里,Pio 都不得不委托冒险者去帮她收集素材,每天收集到的素材价格为 $a_1,a_2,\ldots,a_n$,再根据素材的价格卖给他们价格最相近的药水。Pio 会在每天晚上用收集到的素材做很多很多瓶药水,而每瓶药水的价格和素材的价格都是一样的(药水制作也是技术活,而且所有人都是要赚钱的嘛!绝对不是什么黑心药商啦~)。假设第 $i$ 天 Pio 卖出的药水与得到的素材的差价的绝对值为 $b_i=\min\limits_{1\leq j<i}|a_i-a_j|$,Pio 想要知道这 $n$ 天里素材与药水的差价绝对值之和 $\sum\limits_{i=1}^{n} b_i$ 。当然,第一天什么素材也没有,冒险者自然是无法向 Pio 购买药水的,所以第一天的差价 $b_1=a_1$ 。

输入格式

第一行是一个正整数 $T$,表示测试数据的组数。接下来有 $T$ 行,每行表示一组测试数据。每行以一个正整数 $n$ 开始,表示 Pio 向冒险者委托的天数;然后是 $n$ 个非负整数,依次表示每天收集到素材的价格 $a_1,a_2,\ldots,a_n$ 。

输出格式

每组测试数据一行,输出 $n$ 天里素材与药水的差价绝对值之和 $\sum\limits_{i=1}^{n} b_i$ 。

样例输入

2 5 1 2 3 4 5 7 2 9 7 4 6 2 6

样例输出

5 14

数据范围

$1\leq T\leq 10$, $1\leq n\leq10^5$, $0≤a_i\le 65536$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!