【u242】排名系统

Time Limit: 1 second
Memory Limit: 64 MB

【问题描述】

F1的影响力越来越大,因此国际汽联决定扩大规模,让更多有天赋的车手加入这一行列。
不过规模的扩大带来了一系列问题,比如排名系统。由于参赛人数过多,排名系统要运行很久才能够得出结果。
车迷们非常愤怒,强烈要求修改系统。于是,汽联召开紧急会议,决定在短期内重新编写该系统。
F1排名的标准是:每场比赛的前八名可获得积分,从第一名到第八名分别获得:10,8,6,5,4,3,2,1个积分,车手总积分
是该车手各场比赛获得的积分之和。每场比赛过后,排名系统都会将当前的车手总积分从大到小排序,若积分相等则编号小的车
手排在前面。
你的任务就是要编写这一系统。不过车迷们常常只关注第一名,因此,你只需在每场比赛过后输出排名第一的车手的编号即可。


【输入格式】

输入文件rank.in。第一行是两个整数n,m(8<=n<=1000000,1<=m<=1000000),分别表示车手数和比赛场数。接下来m行,每行八
个整数,第i行第j个是rij(1<=rij<=n),表示第i场比赛获得第j名的车手的编号。

【输出格式】

输出文件rank.out。m行,第i行是一个整数ci,表示第i场比赛结束后排名第一的车手的编号。

【数据规模】

30%的数据满足n<=1000,m<=1000

Sample Input1

  14 3
    1 4 14 8 10 6 12 7
    4 6 14 8 3 11 1 13
    1 11 14 8 10 3 9 12





Sample Output1

1
4
1

【题解】

因为只需要获取第一名的信息。所以在一边读数据的时候,一边维护一下最大值就可以了。其他值可以不用管。用一个a[1..n]数组来表示每名选手的成绩(只占6M),每次读到一

一名选手,就根据成绩加上分数就可以了。然后和最大值进行比较。如果大于则更新最大值。相等则根据编号,如果编号更小则更新一下编号。每输入一行就输出一行。

【代码】

#include <cstdio>
#include <cstring>

const int dx[9] = {0,10,8,6,5,4,3,2,1};

int a[1000001],n,m,maxn,maxdata;

void input_data()
{
	scanf("%d%d",&n,&m);
	for (int j = 1;j <= 8;j++) //先预处理一下只进行一场比赛的情况,先处理出第一场比赛之后的得分情况和第一名 
		{
			int x;
			scanf("%d",&x);
			a[x] += dx[j];
			if (j == 1)
				{
					maxn = x;
					maxdata = 10;	
				}
		}
	printf("%d
",maxn);
}

void get_ans()
{
	for (int i = 2;i <= m;i++) //然后再进行接下来的比赛.这下就可以根据得分情况与最大值进行比较。 
		{
			int temp;
			for (int j = 1;j <= 8;j++) //只有前8名才有得分。 
				{
					scanf("%d",&temp);	
					a[temp]+=dx[j];
					if (a[temp] > maxdata)
						{
							maxn = temp;
							maxdata = a[temp];
						}	
						else //如果分数相同,编号小的还可以更新编号。 
							if (a[temp] == maxdata && temp<maxn)
								maxn = temp;
				}
			printf("%d
",maxn);
			
		}
}

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	get_ans();
	return 0;	
}


原文地址:https://www.cnblogs.com/AWCXV/p/7632401.html