ACM and STL-DNA Sorting

ACM and STL

DNA Sorting

Time Limit: 1000ms Memory Limit: 10000K

Description

One measure of `` unsortedness '' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence `` DAABEC '', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence `` AACEDGG '' has only one inversion (E and D) --- it is nearly sorted --- while the sequence `` ZWQM '' has 6 inversions (it is as unsorted as can be --- exactly the reverse of sorted). You are responsible for cataloguing a sequence of DNA strings (sequences containing only the Four Letters A, C, G, AND T). However, you want to catalog the, not in alphabetical order, but rather in order of `` sortedness' ', from `` Most sorted' 'to `` Least sorted' All the strings are of the same length.

INPUT

THE FIRST LINE CONTAINS TWO INTEGERS: A POSITIVE INTEGER N (0

OUTPUT

Output the list of infut strings, arranged from `` Most sorted '' to `` Least sorted '' '. Since Two strings can be equally sorted, the Output the According to the Orginal ORDER.

Sample Input

10 6

Aacatgaagg

TTTTGGCCAA

TTTGGCCAAA

GatcaGattt

Cccgggggga

Atcgatgcat

Sample Output

Cccgggggga

Aacatgaagg

GatcaGattt

Atcgatgcat

TTTTGGCCAA

TTTGGCCAAA

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!!!!!!

// by lingch

// 2005-3-19

Analysis

This is a sort problem. As stated, we may first cagculate the inversions of each string, and then sort the strings..

SourceMemory: 88k Time: 0mslanguage: C Result: Accepted

#Include

· #Include

· #Include

·

Using Namespace Std;

·

· INT N, M;

·

· Class MyString

{

· Public:

INT length;

INT INV;

· CHAR STR [50];

·

Mtring ()

·: Length (0)

·, INV (0)

{

· STR [0] = 0;

}

·

· Mystring & operator = (const myString & s);

·

· Friend Istream & Operator >> (ISTREAM & IS, MYSTRING & ISTR);

· Friend Ostream & Operator << (Ostream & OS, MyString & Ostr);

}

·

· IStream & Operator >> (ISTREAM & IS, MYSTRING & ISTR)

{

· INT I, J;

· Istr.length = n;

· For (i = 0; i

· IS >> istr.str [i];

· Istr.Str [istr.length] = 0;

·

// Here Calculate The Inversion of this string

· Istr.inv = 0; · for (i = 0; I

{

· For (j = i 1; j

{

· IF (istr.str [i]> istr.str [j])

· Istr.inv ;

}

}

· Return IS;

}

·

· MyString & MyString :: Operator = (const mystring & sr)

{

· IF (& SR! = This)

{

· Copy (& Sr.STR [0], & sr.str [length], this-> str);

· INV = Sr.inv;

· Length = Sr.LENGTH;

}

· Return * this;

}

·

· Ostream & Operator << (Ostream & OS, MyString & OStr)

{

INT I;

· For (i = 0; i

· OS << Ostr.STR [I];

· Return OS;

}

·

· // this predicate use the inversion of the string as the sort key

· BOOL MYPRE (MyString S1, MYSTRING S2)

{

· IF (s1.inc

· Return True;

· Else

· Return False;

}

·

INT main ()

{

· INT I; · CIN >> N >> m;

·

Vector ss;

· For (i = 0; i

{

· Mystring s;

· CIN >> S;

· SS.PUSH_BACK (S);

}

·

· Sort (ss.begin (), ss.end (), mypre;

·

· For (i = 0; i

· Cout << SS [i] << endl;

·

· // System ("pause");

}