1056. Mice and Rice (25)-PAT甲级真题

当时没想到可以用队列来做，就傻傻的模拟了，用cur存当前轮的id，这个id对应的是order的下标，这里有个求rank的技巧就是当前轮没有晋级的rank为（当前轮的组数+1）

模拟：

#include<bits/stdc++.h>
using namespace std;
struct node{int id,w,rk=0;
};
vector<node> vec;
vector<int> order,cur; //cur用来记录当前晋级的组里面的id，对应order数组的下标
int np,ng;
bool cmp(node&a, node& b){return a.rk>b.rk;
}
int main(){scanf("%d%d",&np,&ng);vec.resize(np);order.resize(np);cur.resize(np);for(int i=0;i<np;i++){scanf("%d",&vec[i].w);vec[i].id=i;cur[i]=i;}for(int i=0;i<np;i++)scanf("%d",&order[i]);if(cur.size()==1){printf("1");return 0;}while(cur.size()>1){int start=0;vector<int> temp;int numg; //当前分组数if(cur.size()%ng!=0) numg=cur.size()/ng+1;else numg=cur.size()/ng;while(start<cur.size()){int max=-1,maxi=0;for(int i=start;i<start+ng&&i<cur.size();i++){vec[order[cur[i]]].rk=numg+1;if(max<vec[order[cur[i]]].w){max=vec[order[cur[i]]].w;maxi=i;}}vec[order[cur[maxi]]].rk=numg==1?1:numg+1;temp.push_back(cur[maxi]);start+=ng;}cur=temp;}sort(vec.begin(),vec.end(),[](node& a,node& b){return a.id<b.id;});for(int i=0;i<vec.size();i++)printf(i==0?"%d":" %d",vec[i].rk);return 0;
}

柳神的队列做法：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct node {int weight, index, rank, index0;
};
bool cmp1(node a, node b) {return a.index0 < b.index0;
}
int main() {int n, g, num;scanf("%d%d", &n, &g);vector<int> v(n);vector<node> w(n);for(int i = 0; i < n; i++)scanf("%d", &v[i]);for(int i = 0; i < n; i++) {scanf("%d", &num);w[i].weight = v[num];w[i].index = i;w[i].index0 = num;}queue<node> q;for(int i = 0; i < n; i++)q.push(w[i]);while(!q.empty()) {int size = q.size();if(size == 1) {node temp = q.front();w[temp.index].rank = 1;break;}int group = size / g;if(size % g != 0)group += 1;node maxnode;int maxn = -1, cnt = 0;for(int i = 0; i < size; i++) {node temp = q.front();w[temp.index].rank = group + 1;q.pop();cnt++;if(temp.weight > maxn) {maxn = temp.weight;maxnode = temp;}if(cnt == g || i == size - 1) {cnt = 0;maxn = -1;q.push(maxnode);}}}sort(w.begin(), w.end(), cmp1);for(int i = 0; i < n; i++) {if(i != 0) printf(" ");printf("%d", w[i].rank);}return 0;
}