【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


【题解】

因为只需要获取第一名的信息。所以在一边读数据的时候，一边维护一下最大值就可以了。其他值可以不用管。用一个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\n",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\n",maxn);

		}

}

int main()

{

	//freopen("F:\\rush.txt","r",stdin);

	input_data();

	get_ans();

	return 0;

}

巴特西