北大ACM 1007 DNA Sorting
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
//#define MAXFORVALUE 1000 // 所能容纳的最大权值
using namespace std;
typedef pair<string, int> PAIR;
string *str=NULL;
map<string, int> result;
int count_num=0;
int size = 0;
bool flag = false; // 是否有重复字串出现的标志位
string *repeat = new string[50];
int repeat_num = 0;
void InputMessage();
void SortForValue();
void OutputMessage();
int main()
{
InputMessage();
SortForValue();
OutputMessage();
//int f;
//cin >> f;
return 1;
}
int cmp(const PAIR& x, const PAIR& y)
{
return x.second < y.second;
}
void OutputMessage()
{
map<string, int>::const_iterator map_it = result.begin();
vector<PAIR> vecpair;
for(map<string, int>::iterator curr = result.begin(); curr != result.end(); ++curr)
{
vecpair.push_back(make_pair(curr->first, curr->second));
}
sort(vecpair.begin(), vecpair.end(), cmp);
for(unsigned int i=0; i < vecpair.size(); i++)
{
if(flag)
{
for(int j = 0; j < repeat_num; j++)
{
if(vecpair[i].first == repeat[j])
{
for(int k = 0; k < 2; k++)
cout << vecpair[i].first << endl;
}
}
}else {
cout << vecpair[i].first << endl;
}
}
}
void SortForValue()
{
int value = 0; //得到字串的权值
for(int i=0; i<count_num; i++)
{
for(int j=0; j < size; j++)
{
for(int k=j+1; k <size; k++)
{
if(str[i][j] > str[i][k])
{
value++;
}
}
}
pair<map<string, int>::iterator, bool> ret =
result.insert(make_pair(str[i], value));
if(!ret.second)
{
flag = true;
repeat[repeat_num] = str[i];
repeat_num++;
}
//cout << "第" << i+1 << "个权值为" << value << endl;
value = 0;
}
}
void InputMessage()
{
cin >> size >> count_num;
str = new string[count_num];
for(int i=0; i < count_num; i++)
cin >> str[i];
}
