PAT-2020年春季考试-甲级 7-4 Replacement Selection (30分)

优先队列解法

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+9, INF=1e9;
int n, m;
struct node{int v, id;friend bool operator < (node a, node b){return a.id == b.id ? a.v>=b.v : a.id>=b.id;};
};
vector<int> q[maxn];   // 存 run
int main()
{priority_queue<node, vector<node> > pq;  // 充当“内存”cin >> n >> m;while(pq.size()<m && pq.size()<n){   // 先填满“内存”int t; scanf("%d", &t);pq.push({t, 1});}for(int i = pq.size(); i < n; i++){  // 开始读入剩下的数据int t; scanf("%d", &t);node preout = pq.top();  // 靠前的run里最小的数出列pq.pop();q[preout.id].push_back(preout.v);t < preout.v ? pq.push({t,preout.id+1}) : pq.push({t, preout.id});   // 下一个进来的数和出去的比较，小了就不是一个run，大了就是同一个run}while(!pq.empty()){         // 榨干优先队列node u = pq.top();q[u.id].push_back(u.v);pq.pop();}int i = 1;while(q[i].size()>0){       // 从1st run开始遍历, id都是逐项加1, 所以q[i].size()==0就结束了for(int j = 0; j < q[i].size(); j++){if(j) putchar(' ');printf("%d", q[i][j]);}cout << endl;i++;}return 0;
}