最大间隙

最大间隙

时间限制：10 sec

空间限制：1 GB

问题描述

给定长度为 n 的数组 a，其中每个元素都为 [0,2^k) 之间的整数，请求出它们在实数轴上相邻两个数之间的最大值（即maxGap）。

由于 n 可能很大，为了避免过大的输入、输出规模，我们会在程序内部生成数据，并要求你输出排序后序列的哈希值。具体方法如下（用 c++代码展示）：

输入将会给定 n,k,seed。

你可以调用 initData(a,n,k,seed) 来获得需要排序的 a 数组。

输入格式

一行 3 个用空格隔开的整数 n,k,seed，意义见题目描述。

输格式

一行一个整数，表示最大间隙（即maxGap）。

样例输入

样例输

样例解释

生成的序列应为 4 10 13 9 4，最大间隙为 9-4=5。

数据范围

本题共设置 4 组数据。

对于第 1 组数据，保证 n=1000，k=16。对于第 2 组数据，保证 n=5*10^6，k=32。

对于第 3 组数据，保证 n=2^26=67,108,864，k=16。对于第 4 组数据，保证 n=2^26=67,108,864，k=32。保证给定的 seed 在 32 位无符号整数的范围内。

提示

[对于 k=16 的数据，使用桶排序即可。]

[对于 k=32 的数据，可以用邓老师上课讲的算法哦！]

[进一步地，如何设置桶的大小来避免较慢的除法运算呢？（提示：可以考虑位运算！）]

代码

#include <bits/stdc++.h> using namespace std;

// ================= 代码实现开始 =================

typedef unsigned int u32;

// 以下代码不需要解释，你只需要知道这是用于生成数据的就行了u32 nextInt(u32 x) {

x ^= x << 13;

x ^= x >> 17;

x ^= x << 5;

return x;

}

void initData(u32* a, int n, int k, u32 seed) {

for (int i = 0; i < n; ++i) {

seed = nextInt(seed);

a[i] = seed >> (32 - k);

}

}

// 以上代码不需要解释，你只需要知道这是用于生成数据的就行了const int N = 67108864;

u32 a[N + 1];

u32 l[N + 1], r[N + 1];

// 这是求解答案的函数，你需要对全局变量中的 a 数组求解 maxGap 问题

// n, k：意义与题目描述相符

// 返回值：即为答案（maxGap） u32 maxGap(int n, int k) {

const int m = 1 << 26;

memset(l, -1, sizeof(int)*m);

memset(r, -1, sizeof(int)*m);

const int _k = max(k - 26, 0);

for (int i = 0; i < n; ++i) {

u32 bl = a[i] >> _k;

if (l[bl] == -1)

l[bl] = r[bl] = a[i];

else if (a[i] < l[bl])

l[bl] = a[i];

else if (a[i] > r[bl])

r[bl] = a[i];

}

u32 last = a[0];

u32 ans = 0;

for (int i = 0; i < m; ++i)

if (l[i] != -1) {

if (last > l[i])

last = l[i];

if (l[i] - last > ans)

ans = l[i] - last;

last = r[i];

}

return ans;

}

// ================= 代码实现结束 =================

int main() {

    int n, k;

    u32 seed;

    scanf("%d%d%u", &n, &k, &seed);

    initData(a, n, k, seed);

    u32 ans = maxGap(n, k);

    printf("%u\n", ans);

    return 0;

}