PAT（甲级）2020年春季考试 7-4 Replacement Selection

这种复杂的模拟题，对于我这种菜鸡，只能是根据自己的理解，去把题目给演示出来，然后结合测试用例，一点一点debug+打印输出，的确耗时，所以考试要是遇到就放最后吧。

把这题做出来，我的一个收获是，学会了用优先队列对结构体进行排序。

本题我用一个结构体类型的priority_queue模拟那个关键的内存。对于每个结点，都有2个属性，数据和标签，标签代表这个结点属于哪一批被排序。也是最后输出的依据。

本题的关键点就在于，一个待进入的数字，可能不是这一批的，但是又一定会进入。所以结构体排序的依据就是先让批次小的浮上来，再让数值小的浮上来。

第一次得分是10/30。还遇到一个运行时错误，说明可能有越界访问，我加了一个队列的判空，于是那个用例变成了答案错误。

去看别人的代码，我受到启发，我以内存是否为空为主线程，后来因为读不全被迫加上判断是否所有的元素都进入了。为什么不换种思路，把读入全部数据作为主线程呢？担心内存最后还有元素剩余，再后补一个while循环即可。便有了第二次的AC程序。

也由此，我又得到一个宝贵经验，主线程的选择十分重要。别的可以修修补补。并列比嵌套容易处理。

第一次程序

#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>using namespace std;const int maxn = 100010;//81, 94, 11, 96, 12, 99, 35
//[81 94 11] 96 12 99 35
//run1:11  [81 94 96] 12 99 35
//run1:11 81 run2:12  [94 96 12] 99 35
//run1:11 81 94 run2:12 [96 99 12] 35
//run1:11 81 94 96 run2:12 35 [35 99 12]
//run1:11 81 94 96 99 run2:12 35//13 3
//81 94 11 96 12 99 17 35 28 58 41 75 15
//run1:81 94 11 [81 94 11]
//run1:81 94 11 96 [81 94 96]
//run1:81 94 11 96 run2:12 [94 96]
//run1:81 94 11 96 99 run2:12 [99 96]
//run1:81 94 11 96 99 run2:12 17 [99]
//run1:81 94 11 96 99 run2:12 17 35 []
//run1:81 94 11 96 99 run2:12 17 35 [12 17 35]
//run1:81 94 11 96 99 run2:12 17 35 28[28 17 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58[28 58 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58 41[41 58 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58 41 75[41 58 75]struct Node{int data;int label;friend bool operator < (Node a,Node b){if(a.label!=b.label)return a.label>b.label;else return a.data>b.data;} Node(int _data,int _label):data(_data),label(_label){}
};vector<Node> vi;//存放读入 priority_queue<int,vector<int>,greater<int> > run[maxn];//存放结果 priority_queue<Node> RS;//模拟内存空间 int main(){int n,L,label = 1;scanf("%d %d",&n,&L);for(int i=0;i<n;i++){int data;scanf("%d",&data);Node node = Node(0,0);if(i<L){node = Node(data,label);//前L个元素一定在第一轮RS.push(node);}else{node = Node(data,0); }vi.push_back(node);  }int q = L;//vi[q] int left = 0;//剩余的存储空间 //test
//	printf("初始:RS内存中的可进入空间为为%d\n",left); 
//	printf("RS内存中的已有元素为%d\n",RS.size());
//	printf("\n");while(RS.size()!=0||q<n){Node node = RS.top();int data = node.data;int nLabel = node.label;run[nLabel].push(data);RS.pop();if(nLabel == label)left ++;if(left==0){label ++;printf("改朝换代了\n\n");continue; }//test
//		printf("经过弹出:RS内存中的元素大小为%d\n",left);
//		printf("RS内存中的已有元素为%d\n",RS.size()); 
//		printf("\n");if(q<n){if(vi[q].data>=data){vi[q].label = label;RS.push(vi[q]);left --;}else{vi[q].label = label+1;RS.push(vi[q]);left --;}q++;}//test
//		printf("经过放入:RS内存中的元素大小为%d\n",left);
//		printf("RS内存中的已有元素为%d\n",RS.size()); 
//		printf("\n");}for(int i=1;i<=label+1;i++){int size = run[i].size();int out = 0;while(!run[i].empty()){printf("%d",run[i].top());out++;if(out<size)printf(" ");else printf("\n");run[i].pop();}}return 0;
}

第一次结果

第二次程序(AC代码)

#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<set>
#include<vector>
#include<queue>using namespace std;const int maxn = 100010;//81, 94, 11, 96, 12, 99, 35
//[81 94 11] 96 12 99 35
//run1:11  [81 94 96] 12 99 35
//run1:11 81 run2:12  [94 96 12] 99 35
//run1:11 81 94 run2:12 [96 99 12] 35
//run1:11 81 94 96 run2:12 35 [35 99 12]
//run1:11 81 94 96 99 run2:12 35//13 3
//81 94 11 96 12 99 17 35 28 58 41 75 15
//run1:81 94 11 [81 94 11]
//run1:81 94 11 96 [81 94 96]
//run1:81 94 11 96 run2:12 [94 96]
//run1:81 94 11 96 99 run2:12 [99 96]
//run1:81 94 11 96 99 run2:12 17 [99]
//run1:81 94 11 96 99 run2:12 17 35 []
//run1:81 94 11 96 99 run2:12 17 35 [12 17 35]
//run1:81 94 11 96 99 run2:12 17 35 28[28 17 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58[28 58 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58 41[41 58 35]
//run1:81 94 11 96 99 run2:12 17 35 28 58 41 75[41 58 75]struct Node{int data;int label;friend bool operator < (Node a,Node b){if(a.label!=b.label)return a.label>=b.label;else return a.data>=b.data;} Node(int _data,int _label):data(_data),label(_label){}
};vector<int> vi;//存放读入 priority_queue<int,vector<int>,greater<int> > run[maxn];//存放结果 priority_queue<Node> RS;//模拟内存空间 int main(){int n,L,label = 1;scanf("%d %d",&n,&L);for(int i=0;i<n;i++){int data;scanf("%d",&data);Node node = Node(0,0);if(i<L){node = Node(data,label);//前L个元素一定在第一轮RS.push(node);}else{node = Node(data,0); }vi.push_back(data);  }int q;//vi[q] int dead = 0;//已死内存 for(q=L;q<n;q++){Node now = RS.top();int nData = now.data;int nLabel = now.label;run[nLabel].push(nData);RS.pop(); int cData = vi[q];if(cData>=nData){Node node = Node(cData,label);RS.push(node);}else{Node node = Node(cData,label+1);RS.push(node);dead ++;if(dead == L){label ++;//改朝换代了 dead = 0;//清零 } }}while(!RS.empty()){//还有没出内存的 Node now = RS.top();int nData = now.data;int nLabel = now.label;run[nLabel].push(nData);RS.pop();  } //检验成果的时候到了 int i = 1;while(run[i].size()>0){int size = run[i].size();int out = 0;while(!run[i].empty()){printf("%d",run[i].top());out++;if(out<size)printf(" ");else printf("\n");run[i].pop();}i ++;}return 0;
}

第二次结果