3698 - 最慢的快排
描述

小 nod 新学了快速排序，并且学会了用 random 函数获取随机中枢避免最坏复杂度。代码如下：

void Qsort(int a[], int low, int high) {     if(low >= high) return;     int first = low;     int last = high;     int key_index = (rand() % (high - low + 1)) + low;     swap(a[first], a[key_index]);     int key = a[first];     while(first < last) {         while(first < last && a[last] >= key) --last;         a[first] = a[last];         while(first < last && a[first] <= key) ++first;         a[last] = a[first];     }     a[first] = key;     Qsort(a, low, first - 1);     Qsort(a, first + 1, high); }

号称这份代码跑得比谁都快。夹克老爷为了教育他，构造了大小为 k 的数组 r，使得快排开始后，第 i 次调用 rand 函数时返回的是 r[i%k]（这里 i 从 0 开始，即简单地按从前往后循环使用 r 数组）。
给出 r 数组中的 k 个数，你能构造一个 1~N 的排列，让测试机上运行的快排代码递归调用深度最大吗？（Qsort 函数的递归调用深度最大，不考虑尾递归优化）。
输出递归深度最大的排列中字典序最小的那个排列。
例如 N=3, k=1, r=[0]：每次选择第 0 个数字作为枢轴，最大递归 3 层，(1,2,3)、(3,2,1)、(3,1,2) 等都符合，其中字典序最小的是 (1,2,3)，答案为 1 2 3。

输入

第一行两个整数 N, K（1 <= N <= 50000, 1 <= K <= 50000）。
第 2 ~ K+1 行：每行 1 个数，对应数组 r 中的元素（0 <= r[i] <= 10^9）。

输出

一行 N 个整数，1~N 的一个排列，使得上述快排代码递归深度最大，输出其中字典序最小的那个排列。

样例

输入

3 1
0

输出

1 2 3

输入

3 1
1

输出

1 3 2

输入

4 2
1
2

输出

1 4 3 2
提示

每次中枢选中当前段的最大值或最小值可只排除一个数字，从而得到最大递归深度。为使字典序最小，中枢位置确定后：若该位置左边还有未填数字则此处放当前最大值、把最小值留给更靠左的位置，否则放最小值。注意正确复刻题面代码中与 first 交换、以及回填枢轴的逻辑。（本题评测数据规模较小 N<=9）

来源
51nod 1377
标签
模拟 构造 快速排序 提高
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过次数 0
统计
上一题
下一题