第42页 竞赛记分板第十五

这道题是数组做静态线性表的应用，外加一点排序。

需要三个线性表：一个三维数组记录每个状态为C或I的条目，一维下标为队号，二维下标为题号，第三维两个元素，第一个表征是否已解决，若已解决存放第一次解决的时间，第二个记录在第一次解决前有几次Incorrect的提交；一个一维数组，记录每个队是否提交了；一个二维数组记录全部有提交记录的队伍的成绩，第二维有3个元素，第一个是队号，第二个是解了几道题，第三个是累计时间。

处理输入，更新前两个线性表。根据这两个线性表，更新第三个，然后再将它按规则排序后，输出结果。

使用合并排序，因为n的规模到了100，交换与比较（三元组）又较耗时，所以合并排序会比插入排序省时。

代码如下：
#include <stdio.h>
#include <string.h>
static int comp(int a[3], int b[3])
{
	if (a[1] != b[1])
		return a[1] - b[1];
	else if (a[2] != b[2])
		return b[2] - a[2];
	else
		return b[0] - a[0];
}
static void merge(int (*A)[3], int p, int q, int r)
{
	int n1 = q - p + 1;
	int n2 = r - q;
	int L[n1 + 2][3];
	int R[n2 + 2][3];
	int i, j, k;

	for (i = 1; i <= n1; i++) {
		L[i][0] = A[p + i -1][0];
		L[i][1] = A[p + i -1][1];
		L[i][2] = A[p + i -1][2];
	}
	for (j = 1; j <= n2; j++) {
		R[j][0] = A[q + j][0];
		R[j][1] = A[q + j][1];
		R[j][2] = A[q + j][2];
	}
	L[i][0] = 101;
	L[i][1] = 0;
	L[i][2] = 0;
	R[j][0] = 101;
	R[j][1] = 0;
	R[j][2] = 0;
	i = 1;
	j = 1;
	for (k = p; k <= r; k++) {
		if (comp(L[i], R[j]) > 0) {
			A[k][0] = L[i][0];
			A[k][1] = L[i][1];
			A[k][2] = L[i][2];
			i++;
		} else {
			A[k][0] = R[j][0];
			A[k][1] = R[j][1];
			A[k][2] = R[j][2];
			j++;
		}
	}
}
static void merge_sort(int (*A)[3], int p, int r)
{
	if (r > p) {
		int q = (p + r) / 2;
		merge_sort(A, p, q);
		merge_sort(A, q + 1, r);
		merge(A, p, q, r);
	}
}
int main(int argc, const char **argv)
{
	int actions[101][10][2];
	int sd[101];
	int scores[101][3];
	int cases;
	int nr_sd;
	int c, p, t, l;
	int i, j;
	int solved, ptime;

	scanf("%d\n", &cases);
	while (cases-- > 0) {
		memset(sd, 0, sizeof(sd));
		memset(actions, 0, sizeof(actions));
		while ((c = getchar()) != '\n' && c != EOF) {
			ungetc(c, stdin);
			scanf("%d %d %d ", &c, &p, &t);
			sd[c] = 1;
			l = getchar();
			if (l == 'C' && !actions[c][p][0])
				actions[c][p][0] = t;
			else if (l == 'I' && !actions[c][p][0])
				actions[c][p][1] += 1;
			if (getchar() == EOF)
				break;
		}
		nr_sd = 0;
		for (i = 1; i <= 100; i++) {
			if (!sd[i])
				continue;
			nr_sd++;
			scores[nr_sd][0] = i;
			solved = 0;
			ptime = 0;
			for (j = 1; j <= 9; j++)
				if (actions[i][j][0] > 0) {
					solved++;
					ptime += actions[i][j][0];
					ptime += actions[i][j][1] * 20;
				}
			scores[nr_sd][1] = solved;
			scores[nr_sd][2] = ptime;
		}
		merge_sort(scores, 1, nr_sd);
		for (i = 1; i <= nr_sd; i++)
			printf("%d %d %d\n", scores[i][0], scores[i][1], scores[i][2]);
		if (cases > 0)
			putchar('\n');
	}
	return 0;
}