当前位置: 代码迷 >> 综合 >> PAT A1056 Mice and Rice
  详细解决方案

PAT A1056 Mice and Rice

热度:98   发布时间:2024-01-27 00:05:15.0

题目难度:三颗半星
题目大意:给出N个老鼠的体重,然后每K个一组,拿出每组重量最重的继续比较,然后给相应的老鼠排名。
题目坑点:看完题目感觉不难,但是到了排名的时候,困扰了很久,一直以为像之前的模拟题,算出每个老鼠的排名,最后再遍历一遍就好,但是完全不是这样。
这里轮的概念,需要用到队列,即先所有的老鼠进队,然后挨个出队,每出队K个老鼠,就将已经出队的K个老鼠中最重的那个序号继续进队,这里还有一个我没有想到的点就是,出队之后的老鼠,就等于当前分组数加一。仔细一想,确实是这样,因为分成了若干组,每个组需要给出一个最大的,因而这几个的排名就占了当前的分组数,因此,剔除出队的排名自然就是当前的组数+1。

代码如下:(完全是抄的算法笔记。。。害臊)

#include<iostream>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<cstring>
using namespace std;
typedef struct{int weight,rank;
}Mouse;
Mouse mice[1005];
int main(){int N,step;cin>>N>>step;int num;queue<int> q;for(int i=0;i<N;i++){cin>>mice[i].weight;}for(int i=0;i<N;i++){cin>>num;q.push(num);}int temp=N,group;while(q.size()!=1){if(temp%step==0)group=temp/step;elsegroup=temp/step+1;for(int i=0;i<group;i++){int k=q.front();for(int j=0;j<step;j++){if(i*step+j>=temp)break;int front=q.front();if(mice[front].weight>mice[k].weight){k=front;}mice[front].rank=group+1;q.pop();}q.push(k);}temp=group;}mice[q.front()].rank=1;for(int i=0;i<N;i++){cout<<mice[i].rank;if(i!=N-1)cout<<" ";}
}