PAT 1171 Replacement Selection

这一题的大意是给出一种叫做Replacement Selection的排序方法，具体的方案是在给出一个存储器的大小M，当存储器中的元素小于存储器的大小M的时候，不断的读入元素，当元素的数量大于等于M时候，就输出存储器中最小的，并且在这个时候如果输入的元素比当前输出的元素大，就放入到存储器中，接替输出元素的位置，如果比输出元素小，就放在下一轮，当这一轮中存储器中元素输出完之后，把下一轮中的元素输入进存储器中，所有的元素按照同样的方法输出，最后所=所构成的排序序列就是Replacement Selection
输出存储器中最小的，我们可以采用堆来存储，保存下一轮的元素，我们同样可以采用堆来存储，这样当第一轮的元素为空时，我们可以直接交换两个堆实现下一轮的开始，而且采用堆可以快速的按照题目的要求按顺序输出。
完整代码如下：

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;//当输入过大的时候，我们采用外部排序//产生一种排序记录叫做一趟//尽可能读多的记录到存储器中，并且在内部排序它们// 它们把结果写回到一些tape中//每一个运行/趟的大小和存储器的容量是相同的// 第一个记录被输出到tape中，存储器将变得可利用对于另一个记录// 排序以递增的方式，如果下一个记录大于等于我们已经输出的记录// 我们把它放到趟中// 81 94 11 96 12 99 35// 11 81 94 12 96 99 35// 11 81priority_queue<int,vector<int>,greater<int>>q1;priority_queue<int,vector<int>,greater<int>>q2;intN;intM;vector<int>t;intmain(){cin>>N>>M;for(inti=0;i<N;i++){intx;cin>>x;t.push_back(x);if(q1.size()<M){q1.push(x);}}intindex=M;while(q1.size()){intx=q1.top();cout<<q1.top();q1.pop();if(x<=t[index]&&index<N){q1.push(t[index]);index++;}elseif(x>t[index]&&index<N){q2.push(t[index]);index++;}if(q1.empty()){cout<<endl;swap(q1,q2);}else{cout<<" ";}}return0;}

总结：这一题首先得看懂题意，我刚开始都没有看懂题意，不知道到底是按照怎么样的流程输出的，当我们看清题意后，会发现采用堆来存储和输出是十分的方便。之后模拟流程即可。