2012年8月20日

UVa 612 - DNA Sorting

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

typedef struct Value Value;
struct Value{
  int index;
  int meansure;
};

int cmp (const void *a, const void *b) {
  return ((Value*)a) -> meansure - ((Value *)b) -> meansure;
}

int main() {
  int t;
  scanf("%d", &t);
  getchar();
  while (t--) {
    char map[110][110];
    Value v[110];
    int i, j, k, n, m, tmp;
    scanf("%d%d", &n, &m);
    getchar();
    for (i = 0; i < m; i++) {
      v[i].index = i;
      gets(map[i]);
    }
    for (i = 0; i < m; i++) {
      tmp = 0;
      for (j = 0; j < n; j++)
        for (k = j + 1; k < n; k++)
          if (map[i][j] > map[i][k]) tmp++;
      v[i].meansure = tmp;
    }
    qsort(v, m, sizeof(Value), cmp);
    for (i = 0; i < m; i++)
      puts(map[v[i].index]);
    if (t)
      puts("");
  }
  return 0;
}

沒有留言:

張貼留言