高二下期6月9日blackbox【6-10】黑匣子
【问题描述】我们使用黑匣子的一个简单模型，它能存放一个整数序列和一个特别的变量i,在初始时刻；黑匣子为空且i等于0。这个黑匣子能执行一系列的命令，有两类命令：ADD(x)：把元素x放入黑匣子；GET：把i加l的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。
下面的表6—4是一个11个命令的例子：
现需要一个有效的算法处理给定的一系列命令。ADO和GET命令的总教至多有300000个。定义ADO命令的个数为M个，GET命令的个数为N...
【6-10】黑匣子
【问题描述】我们使用黑匣子的一个简单模型，它能存放一个整数序列和一个特别的变量i,在初始时刻；黑匣子为空且i等于0。这个黑匣子能执行一系列的命令，有两类命令：ADD(x)：把元素x放入黑匣子；GET：把i加l的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。
下面的表6—4是一个11个命令的例子：
现需要一个有效的算法处理给定的一系列命令。ADO和GET命令的总教至多有300000个。定义ADO命令的个数为M个，GET命令的个数为N个。我们用下面的两个整数序列描述命令序列：
(1)A(l)，A(2)，…，A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3，1，－4，2，8，－1000，2)。
(2)u(1),u(2),…,u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1，2，6，6)。
你可以假定自然数序列u(1),u(2),…,u(N)以非降序排列，N≤M，且对于每一个p(l≤p≤N)有P≤n(p)≤M。
输入；
输入文件名为blackbox.in,其中第一行存放M和N的值，第二行存放A(1)，A(2)，…，A(M)，第三行存放u(1)，u(2)，…，u(N)。
输出：
输出黑匣子的处理结果。
【问题分析】显然．此题实际上已经给出了程序基本的算法流程如下：
当然．此题远没有这么简单。上面程序中的两个过程：ADD和GET是要我们自己去编写的．而且．这两个过程的效率直接决定了整个程序的效率。如果这两个过程都能够应付上限为30000的测试数据．那么整个算法就是成功的。
凭直觉我们就能够发现．上述两个过程的关键在于数据结构的选择。我们先采用最常用的线性表来解题：最基本的想法是不考虑黑匣子内数的有序性，每执行一次GET命令就把黑匣子内的数全部排一个序。这样不难求出ADD过程的时同复杂度为O(1)．而GET过程的时间复杂度为O(Mlog+M)。这样，整个程序的时同复杂度就为0(M+MNlog2M)，我们认为这是一个O(N2log2N)的算法,在N的上限为30000时是绝对不可采用的。
显然．我们完全可以时刻保持黑匣子内数的有序性，这样．GET命令的时同复杂度就被降到了O(1)。但是．在执行ADD命令时，我们需要使黑匣子内的数保持有序．这就需要一个插人排序的过程，这样，ADD命令的时间复杂度就应为o(M)。那么,整个程序的时间复杂度为O(M+MN)。我们认为这是一个O(N2)的算法，虽然程序的速度有所提高，但是对于上限为30000的数据，这样的程序效率依然不令人满意．对于极限数据。一般需要约11秒才能出解，这仍然是不能接受的。
因此，我们可以换一种数据结构，采用堆来存储黑匣子内的数并进行运算。堆的重要性质在于堆的根结点的值是堆中全部结点的值中最大(量大堆)或最小(最小堆)的．由此，如果使得堆的根结点就是整个黑匣子中第i大的数．那么程序的效率将提高很多．这里有一个很巧的方法，构造两个堆．一个最大堆．一个最小堆。把黑匣子中的数排序，前i个数放入最大堆中，之后的数放入最小堆中(没有就不放)，这样最大堆的根结点的值就总是黑匣子中第i大的数。接下来我们所要做的就是保证在执行ADD和GET命令之后．两个堆依然保持原有性质。这样,ADD过程实际上是一个往堆中插入元素的过程，其时间复杂摩为O(log2M);GET过程需要调整两个堆的大小(i发生了变化)，也需要进行堆的插入过程。其时间复杂度为O(log2N)，那么，整个程存的时问复杂度为O(Mlog2M+NIong2N)．我们认为这是一个O(NIog2N)的算法，其效率是相当令人满意的，对于极限数据。都可以在O.1秒左右出解。
下面给出使用堆编写的ADD和GET过程：
上面的表6 5给出了在不同数据量下．采用优化后的线性表和采用堆的两种算法的时间性能比较。不难发现．采用堆的算法在大规模数据量上的时间复杂度要明显优于采用线性表的算法，足见堆的优越性。
本文档为【高二下期6月9日blackbox】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483