[アルゴリズム]POJ-ACM DNA Sorting
5542 ワード
http://poj.org/problem?id=1007
Description
One measre of`unsortednes'in sequence is the number of pairs of entries that are out of order with repect to each other.For instance，in the letter sequence`DAABEC's，this measre is 5since D is greater than four letters to its right and E is greaterthan one letter to its right.This mease is caled the number of inversions in the sequence.The sequence`AACEDG'has onlyone inversion(And)(it is as unsorted as can be-exactly the reverse of sorted)
You are reponsible for cataloguing a sequence of DNA streings(sequences containing only the four letters A，C，G，and T).However，you want to catalog them，not in Alphabettical ored，but rathe in thereders'soness's's's.strever's's's's。
Input
The first line contains two integers:a positive integer n(0<=n==50)giving the length of the strigs;and a positive integer m(0<=100)giving the number of stings.These are folled bym.streings.streing of。
Output
Output the list of input stings、arranged from`most sorted'to`least sorted'.Since two stings can be equally sorted、then output the m accoding to the origal order.
Sample Input
本論文は知識共有署名-非商業的使用3.0許諾協議に基づいて許可します。転載、演繹を歓迎します。しかし、本明細書の署名林の羽が舞い上がるを保持しなければなりません。お問い合わせがあれば、手紙をください。
Description
One measre of`unsortednes'in sequence is the number of pairs of entries that are out of order with repect to each other.For instance，in the letter sequence`DAABEC's，this measre is 5since D is greater than four letters to its right and E is greaterthan one letter to its right.This mease is caled the number of inversions in the sequence.The sequence`AACEDG'has onlyone inversion(And)(it is as unsorted as can be-exactly the reverse of sorted)
You are reponsible for cataloguing a sequence of DNA streings(sequences containing only the four letters A，C，G，and T).However，you want to catalog them，not in Alphabettical ored，but rathe in thereders'soness's's's.strever's's's's。
Input
The first line contains two integers:a positive integer n(0<=n==50)giving the length of the strigs;and a positive integer m(0<=100)giving the number of stings.These are folled bym.streings.streing of。
Output
Output the list of input stings、arranged from`most sorted'to`least sorted'.Since two stings can be equally sorted、then output the m accoding to the origal order.
Sample Input
10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCATCCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
， ， STL ， ， ， STL algorithm vector，string， ， ACM STL ， 、 ， ， ， ， ， ， ， 。 #include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
unsigned int NumberOfInversion(const string& str)
{
unsigned int n = 0;
string::const_iterator it = str.begin(),next;
while (str.end() != it)
{
next = it+1;
while (str.end() != next)
{
if (*it > * next)
{
++n;
}
++next;
}
++it;
}
return n;
}
bool compare(const string& str1, const string& str2)
{
if(NumberOfInversion(str1) < NumberOfInversion(str2))
{
return true;
}
return false;
}
void myPrint (const string& str) {
cout <<str<<endl;
}
int main()
{
unsigned int row,col;
cin>>col>>row;
string str;
vector<string> vec;
while (row--)
{
cin>>str;
vec.push_back(str);
}
sort(vec.begin(),vec.end(),compare);
for_each(vec.begin(),vec.end(),myPrint);
return 0;
} 本論文は知識共有署名-非商業的使用3.0許諾協議に基づいて許可します。転載、演繹を歓迎します。しかし、本明細書の署名林の羽が舞い上がるを保持しなければなりません。お問い合わせがあれば、手紙をください。