U431308 Maximum-Gap
题目描述
给你一个长度为 $n$ 的序列 $a$，求它排完序后的 $\max(\lvert a_i-a_{i-1}\rvert)$。
输入格式
第一行，一个正整数 $t$，表示数据组数，一个 64 位无符号种子
接下来 $t$ 行，每行一个正整数 $n$。
输出格式
一个数，表示序列排完序后的 $\max(\lvert a_i-a_{i-1}\rvert)$。
说明/提示
对于所有数据，$n\le 1\times 10^8,\lvert a_i\rvert\le 1\times 10^{18}$。
使用以下数据生成器（用法见注释，样例没用）
```cpp
#include
using namespace std;
namespace DATA {
long long idx;
long long MT[624];
void Seed(long long seed) {
idx = 0;
MT[0] = seed;
for (long long i = 1; i < 624; i++) {
long long t = 1812433253 * (MT[i - 1] ^ (MT[i - 1] >> 30)) + i;
MT[i] = t & 0xffffffffffffffff;
}
}
void generate() {
for (int i = 0; i < 624; i++) {
long long y = (MT[i] & 0x8000000000000000) + (MT[(i + 1) % 624] & 0x7fffffffffffffff);
MT[i] = MT[(i + 397) % 624] ^ (y >> 1);
if (y & 1) MT[i] ^= 2567483615;
}
}
long long Rand() {
if (idx == 0)
generate();
long long y = MT[idx];
y = y ^ (y >> 11);
y = y ^ ((y 18);
idx = (idx + 1) % 624;
return y;
}
}
using DATA::Rand;
using DATA::Seed;
constexpr int N = 1e8 + 3;
long long a[N]; // a in the question
int main() {
int t, n; // n,t in the question
unsigned long long seed; // seed in the question
cin >> t >> seed; // input
Seed(seed); // set seed
while (t--) {
cin >> n; // input
for (int i = 1; i