关于算法-数据结构:PAT甲级2020年春季考试-74-Replacement-Selection

When the input is much too large to fit into memory, we have to do external sorting instead of internal sorting. One of the key steps in external sorting is to generate sets of sorted records (also called runs) with limited internal memory. The simplest method is to read as many records as possible into the memory, and sort them internally, then write the resulting run back to some tape. The size of each run is the same as the capacity of the internal memory.

Replacement Selection sorting algorithm was described in 1965 by Donald Knuth. Notice that as soon as the first record is written to an output tape, the memory it used becomes available for another record. Assume that we are sorting in ascending order, if the next record is not smaller than the record we have just output, then it can be included in the run.

For example, suppose that we have a set of input {81, 94, 11, 96, 12, 99, 35}, and our memory can sort 3 records only. By the simplest method we will obtain three runs: {11, 81, 94}, {12, 96, 99} and {35}. According to the replacement selection algorithm, we would read and sort the first 3 records {81, 94, 11} and output 11 as the smallest one. Then one space is available so 96 is read in and will join the first run since it is larger than 11. Now we have {81, 94, 96}. After 81 is out, 12 comes in but it must belong to the next run since it is smaller than 81. Hence we have {94, 96, 12} where 12 will stay since it belongs to the next run. When 94 is out and 99 is in, since 99 is larger than 94, it must belong to the first run. Eventually we will obtain two runs: the first one contains {11, 81, 94, 96, 99} and the second one contains {12, 35}.

Your job is to implement this replacement selection algorithm.

Each input file contains several test cases. The first line gives two positive integers $N (≤10^5)$ and $M (<N/2)$, which are the total number of records to be sorted, and the capacity of the internal memory. Then N numbers are given in the next line, all in the range of int. All the numbers in a line are separated by a space.

For each test case, print in each line a run (in ascending order) generated by the replacement selection algorithm. All the numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

13 3
81 94 11 96 12 99 17 35 28 58 41 75 15

11 81 94 96 99
12 17 28 35 41 58 75
15

给定一长度为 N 的序列，假如当初内存大小为 M(<N/2)，那么当初须要应用内部排序的置换抉择排序算法对利用该内存空间进行排序输入。

其实就是模仿内部排序的过程，题目举的例子算是说的比拟具体了，模仿的步骤如下：

1、假如待排序的序列存储在 unsorted 队列中，前 M 个元素曾经退出到以后轮次队列 currentRun 待处理，那么只有以后队列不空就进行 2~3 的循环，否则转 4
2、在以后轮的局部有序序列 currentRun 中出队一个元素，并增加到 result 数组中进行暂存，而后再从 unsorted 队列中出队一个元素，如果大于此前进入 result 的元素，进入以后轮次的排序队列 currentRun 中，否则就退出下一轮次的队列 nextRun 中。
3、判断 currentRun 是否为空，如果是，阐明得进入下一轮排序，将 result 进行输入并状况，将 nextRun 赋值给 currentRun 并清空，
4、检测以后轮次排序队列 currentRun 是否全副处理完毕，如果没有就增加进 result 数组中，并输入 result 元素。而后判断下一轮次的队列 nextRun 是否有元素须要解决，如果有就退出到 currentRun 进行排序，而后顺次输入 currentRun 的每一个元素即可。

1、因为每次都得在以后轮次队列中获取最小的元素，那么应用优先队列是最不便的
2、对于测试点 1 和测试点 2 内存超限的状况，有可能是没有及时开释 nextRun 所造成的, 这里将 nextRun 设置为 vector 就必须得开释，然而如果是优先队列的话，就会呈现该问题。
3、判断以后轮为空得在以后轮次处理完毕之后才行，否则测试点 1 谬误或者测试点 2 格局谬误

#include<cstdio>
#include<vector>
#include<queue>
#include<unordered_map>

using namespace std;

priority_queue<int,vector<int>,greater<int> > currentRun;// 以后轮次
queue<int> unsorted;// 待排序局部
vector<int> nextRun;// 暂存下一轮数字
vector<int> result;// 保留每一轮后果

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    // 先将前 M 个数字退出到以后轮次中
    for(int i=0;i<M;++i){
        int num;
        scanf("%d",&num);
        currentRun.push(num);
    }
    // 残余 N - M 个数字退出到待排序序列中
    for(int i=M;i<N;++i){
        int num;
        scanf("%d",&num);
        unsorted.push(num);
    }
    while(!unsorted.empty()){
        // 只有还有数字须要排序
        int temp = currentRun.top();
        currentRun.pop();
        result.push_back(temp);
        // 出队未排序序列元素
        int num = unsorted.front();
        unsorted.pop();
        if(num>result[result.size()-1]){
            // 比上一次出队元素大，在以后轮次
            currentRun.push(num);
        }else{
            // 在下一轮次
            nextRun.push_back(num);
        }
        // 判断以后轮为空得在以后轮次处理完毕之后才行，否则测试点 1 谬误或者测试点 2 格局谬误
        if(currentRun.empty()) {
            // 以后轮为空，须要输入 result，并进行下一轮
            for (int i = 0; i < result.size(); ++i) {printf("%d", result[i]);
                if (i < result.size() - 1) printf(" ");
            }
            printf("\n");
            for (int i:nextRun) {currentRun.push(i);
            }
            nextRun.clear();
            result.clear();}
    }
    // 须要排序的都曾经为空了, 判断以后轮次还有没有处理完毕的
    if(!currentRun.empty()) {while(!currentRun.empty()){
            // 当期轮还有数字没有输入
            int temp = currentRun.top();
            currentRun.pop();
            result.push_back(temp);
        }
        for(int i=0;i<result.size();++i){printf("%d",result[i]);
            if(i<result.size()-1) printf(" ");
        }
        printf("\n");
    }
    if(!nextRun.empty()){
        // 下一轮不空
        for(int i : nextRun){currentRun.push(i);
        }
        // 输入
        while(!currentRun.empty()){int temp = currentRun.top();
            currentRun.pop();
            if(currentRun.empty()){
                // 最初一个元素
                printf("%d",temp);
            }else{printf("%d",temp);
            }
        }
    }
    return 0;
}

关于算法-数据结构:PAT甲级2020年春季考试-74-Replacement-Selection

7-4 Replacement Selection (30 分)

Input Specification:

Output Specification:

Sample Input:

Sample Output:

题目限度：

题目粗心：

算法思路：

留神点：

提交后果：

AC 代码：