1171 Replacement Selection – PAT甲级真题

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.

Input Specification:

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.

Output Specification:

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.

Sample Input:

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

Sample Output:

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

题目大意：当输入数据远远超过内存容量，我们不得不进行外部排序而不是内部排序。外部排序的关键步骤之一是生成一组有限内存的已排序记录（也称为运行集）。最简单的方法是将尽可能多的记录读入内存，对其进行内部排序，然后将生成的运行集写回到某个磁带。每个运行的大小与内部内存的容量相同。替代选择排序算法由Donald Knuth于1965年描述。请注意，一旦第一条记录写入输出磁带，它所使用的内存就会为另一条记录释放出来。假设我们按升序排序，如果下一条记录不比刚刚输出的记录小，那么它可以包含在运行集中。例如，假设我们有一个输入集合{81,94,11,96,12,99,35}，而我们的内存只能排序3条记录。按照最简单的方法，我们将获得三个运行集：{11,81,94}，{12,96,99}和{35}。根据替代选择算法，我们将读取和排序前3条记录{81,94,11} 并输出11作为最小值。然后会有一个空间可用，所以读入96，它会加入第一个运行集，因为它大于11。现在我们有{81,94,96}。81出去后，12进来，但它必须属于下一个运行集，因为它小于81。因此，我们有{94,96,12}，其中12将留在下一个运行集。当94出去，99进来，因为99大于94，它必须属于第一个运行集。最终我们将获得两个运行集：第一个包含{11,81,94,96,99}，第二个包含{12,35}。您的任务是实现这个替代选择排序算法。

分析：A存储输入的数据，创建两个小数先出来的优先队列Q1和Q2，分别表示这一轮正在排序的数列，和下一轮进行排序的数列。index表示当前正在处理的数据的下标，now表示从优先队列里取出来的当前处理的序列段里最小的数。先把M个以内的数据存到Q1里，每次从Q1里取出一个最小的数，并将它输出。看一下下一个要读入的数据（如果有的话）和现在这个最小的数之间的关系。大于等于now，存在Q1里小于现在的now，就把它存到Q2里。如果Q1中的数据全部处理完毕了，就把Q2中的内容交换到Q1里，这样Q1就是下一个要处理的序列段，Q2变成空，可以装新数据。

#include <iostream>
#include <queue>
using namespace std;
int N, M, A[100005], index, now;
priority_queue<int, vector<int>, greater<int>> Q1, Q2;
int main(){
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        if (i <= M) Q1.push(A[i]);
    }
    index = M + 1;
    while (Q1.size()) {
        now = Q1.top();
        cout << now;
        Q1.pop();
        if(index <= N) {
            if (A[index] < now) Q2.push(A[index]);
            else Q1.push(A[index]);
            ++index;
        }
        if (Q1.size()) cout << ' ';
        else {
            swap(Q1, Q2);
            cout << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int N, M, A[100005], index, now;

priority_queue<int, vector<int>, greater<int>> Q1, Q2;

int main(){

cin >> N >> M;

for (int i = 1; i <= N; i++) {

cin >> A[i];

if (i <= M) Q1.push(A[i]);

}

index = M + 1;

while (Q1.size()) {

now = Q1.top();

cout << now;

Q1.pop();

if(index <= N) {

if (A[index] < now) Q2.push(A[index]);

else Q1.push(A[index]);

++index;

}

if (Q1.size()) cout << ' ';

else {

swap(Q1, Q2);

cout << '\n';

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版