// 1007_v001.c
// http://poj.org/problem?id=1007

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

#define MAX_STRING_LEN 56
#define SORTNESS_OFFSET 52
#define MAX_STRING_NUMBER 100

int cmp_fun(const void * a, const void * b){
	// a is a type of char **
	int * sn1 = (int *)(*((char **)a) + SORTNESS_OFFSET);
	int * sn2 = (int *)(*((char **)b) + SORTNESS_OFFSET);
	return *sn1 - *sn2;
}

int main(){
	
	int n;
	int m;
	int i;
	int j;
	int prev_sortedness = 0;
	char prev_char = 0;
	char s[MAX_STRING_NUMBER][MAX_STRING_LEN];
	char * p_s[MAX_STRING_NUMBER];
	int num_in = 0;
	int * p_sortedness;
		
	scanf("%d %d", &n, &m);	
	
	while(scanf("%s", s[num_in]) != EOF ){
		p_sortedness = (int *)(&(s[num_in][SORTNESS_OFFSET]));
		p_s[num_in] = s[num_in];
		*p_sortedness = 0;
		// calculate sortedness
		for(i = 0; i < n; i++){
			if(s[num_in][i] == 'A'){
					
			}else if((i > 0 && i < n) && prev_char == s[num_in][i]){
				(*p_sortedness) += prev_sortedness;
			}else{
				prev_sortedness = 0;
				if(s[num_in][i] == 'C'){
					// Count A
					for(j = i + 1;  j < n; j++){
						if(s[num_in][j] < 'C'){
							(*p_sortedness)++;
							prev_sortedness++;
						}
					}
				}else if(s[num_in][i] == 'G'){
					// Count A C
					for(j = i + 1;  j < n; j++){
						if(s[num_in][j] < 'G'){
							(*p_sortedness)++;
							prev_sortedness++;
						}
					}
				}else if(s[num_in][i] == 'T'){
					// Count A C G
					for(j = i + 1;  j < n; j++){
						if(s[num_in][j] < 'T'){
							(*p_sortedness)++;
							prev_sortedness++;
						}
					}
					
				}
				
			}
			prev_char = s[num_in][i];
		}
		
		num_in++;

	}
	
	
	// qsort
	qsort(p_s, num_in, sizeof(char *), cmp_fun);
	
	for(i = 0; i < num_in; i++){
		if(i == 0)
			printf("%s", *(p_s + i));
		else
			printf("\n%s", *(p_s + i));
		
	}
	
	
	
	return 0;
}

• 算逆序数完成的？不错，我看到这么多人0MS通过，大概都是这个算法吧？ (0) kenden23 2014-04-19 10:18:15