各位好心的高手们，能不能帮帮偶呀？这关系到偶的毕业问题呀～～～～～
呜呜呜～～～偶真的是不会做呢～～～～～～
急呀！！！！！！
这两三天就得上交呀～～～～～～
离线最小值问题：
问题描述：
给定集合S={1，2，…，n}，以及由n个 Insert(x)和 m个 DeleteMin()运算组成的运算序列。其中 n 个 Insert(x)运算将集合 S={1，2，…，n}中每个数插入动态集合 T 恰好一次，DeleteMin()每次删除动态集合T中的最小元素。离线最小值问题要求对于给定的运算序列计算出每个DeleteMin()运算输出的值。换句话说，要求计算数组out，使第i次 DeleteMin()运算输出的值为 out[i]，i=1，2，…，m。在执行具体计算前，运算序列已给定，这就是问题表述中离线的含义。
为了计算输出数组 out 的值，可以用一个优先队列 H，按照给定的运算序列依次执行 n个Insert(x)和m个DeleteMin()运算，将第i次 DeleteMin()运算的结果记录到out[i]中。执行完所给的运算后，数组out即为所求。在最坏情况下，这个算法需要O(mlogn)计算时间。当m=W(n)时，算法需要的计算时间为O(nlogn) 。
实际上，上述算法是一个在线算法，即每次处理一个运算，并不要求事先知道运算序列因而算法没有用到问题的离线性质。利用并查集和问题的离线性质可以将算法的计算时间进一步减少为 O(na(n)) 。
将给定的n个Insert和 m个DeleteMin运算组成的运算序列表示为：I1DI2DI3D…IKDIK+1,
其中I ，1≤j≤k+1，为连续若干个（可以为 0）Insert 运算组成的运算序列，D 表示DeleteMin运算。可用并查集算法模拟这个运算序列。开始时，将I 中的 Insert运算插入动态集合T中的元素用UFunion运算组织成一个集合，并将该集合记为第j个集合，1≤j≤k+1。由于第 j 个集合的名与其序号可能不同，算法中用 2 个数组 si 和 is 来表示集合名与其序号的对应关系。例如，第j个集合名为name时，si[name]=j且 is[j]=name。另外，用2 个数组prev和next来表示I 之间的顺序。开始时，prev[j]=j-1, 1≤j≤k+1且 next[j]=j+1，0≤j≤k。接下来，对每i，1≤i≤n，用UFfind运算计算出集合序号j，使得i∈I 。这表明第j个deleteMin运算输出元素 i，即 out[j]=i。然后用 UFunion 运算将集合I[J]与集合I[J+1] 合并，并修改数组prev和next的值，将j从链表中删除。算法结束后，输出数组out给出正确的计算结果。
编程任务：
对于给定的由 n 个 Insert(x)和 m 个 DeleteMin()运算组成的运算序列，用并查集编程计算出每个DeleteMin()运算输出的值。
数据输入：
由文件input.txt给出输入数据。第一行有 2 个正整数n和 m，分别表示运算序列由n个Insert(x)和 m个 DeleteMin()运算组成。接下来的 1 行中有 n+m个整数。整数 x>0 时表示执行Insert(x)运算；整数x=-1时表示执行 DeleteMin()运算。
结果输出:
将计算出的每个DeleteMin()运算输出的值依次输出到文件 output.txt。
输入文件示例 输出文件示例
input.txt output.txt
10 6 9 10 6 7 8 1
10 9 -1 -1 8 7 6 -1 -1 -1 5 4 3 2 1 -1
[求助]离线最小值问题
