2020年7月第4题 PAT甲级真题 Replacement Selection (30分)

雨点打透心脏的1/2处 2023-03-02 05:26 53阅读 0赞

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

# 题意 #

模拟祖师爷Knuth发明的置换选择排序算法。即，内存一次只能放m个数，给定n(m<n/2)个数，要输出一个或多个有序的序列。算法是要将后(n-m)个数置换内存中的某个数，这个数必须是不小于先前置换的数，从而本轮排序输出序列单调不减；如果找不到这个数，本轮排序完成，进入下一轮排序。重复以上直到所有数字都排好。

# 分析 #

背景很新颖，但是讲明白了就挺简单的。对比[同样背景的算法题][Link 1]，这道题的解释尤其长，相当于难度降低。PAT是C++程序员的语文，读清楚关乎得分。

# 满分代码1 #

这个解法是对题意非常准确的还原，易读性也很好，很高明。

题目说：“内存处理好一个就能容纳下一个。每一轮要吸纳不小于最近输出的数”，于是优先队列q先放前M个数，然后每次都是弹出最小一个，然后读下一个数，符合有序性的话就放本轮处理。

//致谢：https://blog.csdn.net/qq_39072627/article/details/107582244
    #include <cstdio>
    #include <queue>
    #include <vector>
    using namespace std;
    int main() {
        int N, M;
        scanf("%d%d", &N, &M);
        vector<int> arr(N);
        for (int i = 0; i < N; i++) scanf("%d", &arr[i]);
        priority_queue<int, vector<int>, greater<int>> q;//模拟内存的排序，从小到大排列
        vector<int> v,line;//v存放下轮的数；line存放本轮的数
        int index = 0,count=0, last;
        for (; index < M; index++) q.push(arr[index]);
        while (count != N) {//如果从队列里出来的数小于N
            last = q.top();
            line.push_back(last);//根据有序性，每次列头的数会决定arr的下一个数去哪
            q.pop();
            count++;
            if (index < N) {//如果arr里还有数未处理
                if (arr[index] > last) q.push(arr[index++]);
                else v.push_back(arr[index++]);
            }
            if (q.empty()) {//当本轮的数已处理结束，即q为空
                for (int i = 0; i < line.size(); i++) {//输出line
                    if (i != 0) printf(" ");
                    printf("%d", line[i]);
                }
                printf("\n");
                line.clear();
                for (int i = 0; i < v.size(); i++)//v的数全都放到q里
                    q.push(v[i]);
                v.clear();
            }
        }
    }

# 满分代码2 #

思路基本跟上面的一样，只是用map去维持优先队列。

//致谢：https://blog.csdn.net/ziyutongxue/article/details/107582557#comments
    #include<iostream>
    #include<vector>
    #include<map>
    using namespace std;
    int main() {
    	int N, M, val;
    	scanf("%d%d", &N, &M);
    	map<int, int>Ma, Mb;
    	for (int i = 0; i < M; i++) {
    		scanf("%d", &val);
    		Ma[val]++;
    	}
    	vector<int>tmp;
    	vector<vector<int>>ans;
    	for (int i = M; i < N; i++) {
    		scanf("%d", &val);
    		int head = Ma.begin()->first;
    		if(Ma.begin()->second==1)Ma.erase(Ma.begin());
    		else Ma[Ma.begin()->first]--;
    		tmp.push_back(head);
    		if (val >= head)Ma[val]++;//Ma存放本轮
            else Mb[val]++;//Mb存放下一轮
            if (Ma.size() == 0) {//本轮的数都处理好了
                Ma = Mb;
                Mb.clear();
                ans.push_back(tmp);//将本轮的解tmp汇总到ans
                tmp.clear();
            }
            if (i == N - 1) {//到了最后一个数，要将Ma和Mb分别存到解中
    			while (Ma.size()) {
    				tmp.push_back(Ma.begin()->first);
    				if(Ma.begin()->second==1) Ma.erase(Ma.begin());
    				else Ma[Ma.begin()->first]--;
    			}
    			if (tmp.size() > 0)ans.push_back(tmp);
    			tmp.clear();
    			while (Mb.size()) {
    				tmp.push_back(Mb.begin()->first);
    				if (Mb.begin()->second == 1) Mb.erase(Mb.begin());
    				else Mb[Mb.begin()->first]--;
    			}
    			ans.push_back(tmp);
    		}
    	}
    	for (int i = 0; i < ans.size(); i++) {
    		for (int j = 0; j < ans[i].size(); j++) {
    			if (j == 0)printf("%d", ans[i][j]);
    			else printf(" %d", ans[i][j]);
    			if (j == ans[i].size() - 1)printf("\n");
    		}
    	}
    	return 0;
    }

# 测试用例 #

题目中的测试用例输入：

7 3
    81 94 11 96 12 99 35

输出：

11 81 94 96 99
    12 35

[Link 1]: https://blog.csdn.net/PKU_ZZY/article/details/53148630