ZOJ-1188「建议收藏」

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct DNA
{
	char s[51];
	int sort;
	int index;
};

static void calc(struct DNA *p)
{
	char *s = p->s;
	int i, j, c, len = strlen(s);
	p->sort = 0;
	for (i = 0; i < len; i++)
	{
		c = s[i];
		for (j = i + 1; j < len; j++)
			if (c > s[j])
				p->sort++;
	}
}

static int cmp(const void *p1, const void *p2)
{
	struct DNA *d1 = (struct DNA *) p1;
	struct DNA *d2 = (struct DNA *) p2;
	if (d1->sort != d2->sort)
		return d1->sort - d2->sort;
	else
		return d1->index - d2->index;
}

int main()
{
	int t, N;
	scanf("%d", &N);
	struct DNA *array = malloc(100 * sizeof(struct DNA));
	for (t = 0; t < N; t++)
	{
		if (t)
			putchar('\n');
		int n, m;
		scanf("%d %d", &n, &m);
		getchar();
		int i;
		for (i = 0; i < m; i++)
		{
			gets(array[i].s);
			array[i].index = i;
			calc(array + i);
		}
		qsort(array, m, sizeof(struct DNA), cmp);
		for (i = 0; i < m; i++)
			puts(array[i].s);
	}
	free(array);
	return 0;
}