PAT 1056. Mice and Rice

题目：http://pat.zju.edu.cn/contests/pat-a-practise/1056

题意：Np个老鼠，每次最多选Ng个老鼠比较，Ng个中选出体重最大的老鼠进阶下一轮比较。比较有一定次序。

思路：模拟。

代码：

#include<cstdio>
#include<cstring> 
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node
{
   int w,id,lev;
}p[1001];
int order[1001],order1[1001],rankk[1001];
int cmpp(const void *a,const void *b)
{
    return ((node *)b)->lev-((node *)a)->lev;
}
int main()
{
	int n,m,i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	{
		scanf("%d",&p[i].w);
		p[i].id=i;
		p[i].lev=0;
	}
	for(i=0;i<n;i++)
		scanf("%d",&order[i]);
	int count,max,maxi,k=0;
	int tmp=n;
	while(true)
	{
	   max=-1;k=0;count=0;
	   for(i=0;i<tmp;i++)
	   {     
		  if(p[order[i]].w>max)
		  {
			  maxi=i;
			  max=p[order[i]].w;
	      }
		  count++;
		  if(count==m||(i==tmp-1&&count<m))
		  {
			  max=-1;
			  count=0;
			  order1[k++]=order[maxi];
		  }	   
	   }	   
	   for(i=0;i<k;i++)
	   {
		   p[order1[i]].lev++;
		   order[i]=order1[i];
	   }
	   tmp=k;
	   if(k==1) break;
	}
	
	qsort(p,n,sizeof(p[0]),cmpp);
	rankk[p[0].id]=1;
	for(i=1;i<n;i++)
	{
	    if(p[i].lev==p[i-1].lev) rankk[p[i].id]=rankk[p[i-1].id];
		else rankk[p[i].id]=i+1;
	}
	printf("%d",rankk[0]);
	for(i=1;i<n;i++)
		printf(" %d",rankk[i]);
	printf("\n");
	return 0;
}

PAT 1056. Mice and Rice,布布扣,bubuko.com

PAT 1056. Mice and Rice

原文：http://blog.csdn.net/zqh_1991/article/details/21124095