二零一零年第3题

题目地址：http://jobdu.sinaapp.com/problem.php?pid=1007

提供一个测试样例
8 6
4 8 1
6 6 2
4 8 2
2 12 4
7 12 9
2 22 6
3 22 5
9 10 1
0 1 2 4 6 7
实际排序国家以及每次排序结果
4 8 1                 4 4 2 2   2：3
6 6 2                 3 6 3 5   3：1
4 8 2                 4 4 4 4   4：1
7 12 9                2 2 5 6   2：1
3 22 5                6 1 6 3   1：2        
9 10 1                1 3 1 1   1：1

C语言源码：

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100000
typedef struct ran
{
	int a,b;
	double c,d;
	int num;
	int ra;
}ran;
ran r[maxsize];
typedef struct country
{
	int a,b,c;
	int rank[5];
}country;
country c[maxsize];
int cmp1(const void *a,const void *b)
{
	ran *aa=(ran *)a;
	ran *bb=(ran *)b;
	return bb->a-aa->a;
}
int cmp2(const void *a,const void *b)
{
	ran *aa=(ran *)a;
	ran *bb=(ran *)b;
	return bb->b-aa->b;
}
int cmp3(const void *a,const void *b)
{
	ran *aa=(ran *)a;
	ran *bb=(ran *)b;
	return aa->c>bb->c?-1:1;
}
int cmp4(const void *a,const void *b)
{
	ran *aa=(ran *)a;
	ran *bb=(ran *)b;
	return aa->d>bb->d?-1:1;
}
int main()
{
	int n,m,i,stack[maxsize],j,y,l,min,k;
	double x;
	while(scanf("%d %d",&n,&m)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d %d %d",&c[i].a,&c[i].b,&c[i].c);
		for(i=0;i<m;i++)
			scanf("%d",&stack[i]);
		for(i=0;i<m;i++)
		{
			j=stack[i];
			r[i].a=c[j].a;
			r[i].b=c[j].b;
			r[i].c=(double)c[j].a/c[j].c;
			r[i].d=(double)c[j].b/c[j].c;
			r[i].num=j;
		}
		for(k=1;k<=4;k++)
		{
			switch(k)
			{
			case 1:qsort(r,m,sizeof(r[0]),cmp1);break;
			case 2:qsort(r,m,sizeof(r[0]),cmp2);break;
			case 3:qsort(r,m,sizeof(r[0]),cmp3);break;
			default :qsort(r,m,sizeof(r[0]),cmp4);break;
			}
			if(k==1)
			{
				x=-1;
				for(i=0;i<m;i++)
				{
					if(r[i].a!=x)
					{
						r[i].ra=i+1;
						y=i+1;
						x=r[i].a;
					}
					else
						r[i].ra=y;
				}
				for(i=0;i<m;i++)
					c[r[i].num].rank[1]=r[i].ra;
			}
			if(k==2)
			{
				x=-1;
				for(i=0;i<m;i++)
				{
					if(r[i].b!=x)
					{
						r[i].ra=i+1;
						y=i+1;
						x=r[i].b;
					}
					else
						r[i].ra=y;
				}
				for(i=0;i<m;i++)
					c[r[i].num].rank[2]=r[i].ra;
			}
			if(k==3)
			{
				x=-1;
				for(i=0;i<m;i++)
				{
					if(r[i].c!=x)
					{
						r[i].ra=i+1;
						y=i+1;
						x=r[i].c;
					}
					else
						r[i].ra=y;
				}
				for(i=0;i<m;i++)
					c[r[i].num].rank[3]=r[i].ra;
			}
			if(k==4)
			{
				x=-1;
				for(i=0;i<m;i++)
				{
					if(r[i].d!=x)
					{
						r[i].ra=i+1;
						y=i+1;
						x=r[i].d;
					}
					else
						r[i].ra=y;
				}
				for(i=0;i<m;i++)
					c[r[i].num].rank[4]=r[i].ra;
			}
		}
		for(i=0;i<m;i++)
		{
			j=stack[i];
			min=1;
			for(l=1;l<=4;l++)
				if(c[j].rank[l]<c[j].rank[min])
					min=l;
			printf("%d:%d\n",c[j].rank[min],min);
		}
		printf("\n");
	}
}