← 返回比赛

已结束 GESP欢乐赛 #15

← 上一题下一题 →

A1553 | $捞薯条$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Yuilice老家的码头里面下薯条雨了，Yuilice开心的去码头捞了整整$n(1 \leq n \leq 10^5)$箱的薯条，并且准备叫$\frac{n}{k}$辆卡车来运回家。 每辆卡车共会运输$k(1 \leq k \leq n)$箱薯条，例: - 第一辆卡车会运输前$k$箱薯条 - 第二辆卡车会运输第$k+1$ ~ $2 · k$箱薯条 - .... - 第$\frac{n}{k}$辆卡车运输末尾$k$箱薯条 每一辆卡车必须装载$k$箱薯条，否则就无法回程，现在Yuilice需要去考虑运输给出的运费该如何计算，于是他决定运费由这些卡车当中载重最重的卡车与载重最轻的卡车之间重量的差值决定的，差值多少，那么给出的运费就多少。 注意:如果只有一辆卡车，那么差值则为0 现在,Yuilice需要知道,他最多给出的运费为多少呢？

输入格式

输入第一行为一个正整数$t(1 \leq t \leq 10^4)$，代表接下来会有$t$组样例。 随后每组样例的第一行，输入一个正整数$n(1 \leq n \leq 10^5)$，代表共有$n$箱薯条。 随后一行，输入$n$个正整数$a_i(1 \leq a_i \leq 10^9)$代表每箱薯条的重量。

输出格式

输出一个整数，代表Yuilice需要支付的最多运费。

输入输出样例

输入 #1

5
2
1 9
5
100 1 9 8 3 
4
100 100 100 100
7
123 4134123 812389 347213 139238 485123 3217451
4
12395 773418 987321 39218

输出 #1

C++ 编辑器

输入

输出