Skip to content

1184: 置换选择

题目

题目描述

参考书本 P361

现有外存储器中长度为 N 的序列 $a_1,a_2,a_3, ... ,a_N$ 和 大小为 M 的内存

置换选择是一种预处理办法生成若干文件,使得每个文件有序排序(本题中为每个文件升序)

置换选择算法将内存分区为堆和线性表。对于第一个文件,堆一开始占据了整个内存,首先在内存中导入M个数据建堆。之后每次循环,依次pop出堆中最小的元素写入目标文件,再在外存储器数据源中重新补入新的数据,如果新数据大于目标文件最大值则正常放入堆中,否则线性表抢占堆的一格内存并将新数据放入。直到内存全部被线性表占据,则该文件的排序结束,打开新文件并用线性表中的数据重新建堆。重复以上过程直到数据源全部被写入若干排好序的目标文件。

你需要实现以上算法并输出最终产生了多少文件。

输入格式

第一行: 两个数分别为 N,M
第二行: N个数分别为 $a_1,a_2,a_3, ... ,a_N$

输出格式

一个数表示最终的文件数量

样例输入

11 3 1 4 10 2 0 5 7 6 3 9 12

样例输出

2

生成的两个文件依次是1,2,4,5,7,100,3,6,9,12, 具体过程见书本P362

数据范围

N <= 5e5
M <= 1e5
0<=$a_1,a_2,a_3, ... ,a_N$<=2e9 且各不相同

Oops! 本题目还没有解答!

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

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

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