| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:用map<string, multiset<string> * > 以及stl sort,297ms过。In Reply To:用map<string, multiset<string> * > 以及stl sort,297ms过。 Posted by:2007011268 at 2012-08-08 23:18:00 #include <iostream>
#include <map>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
struct Node
{
int size;
multiset<string> * pointer;
};
struct greater_size
{
bool operator()(const Node & a, const Node & b)
{
if(a.size != b.size)
return a.size > b.size;
if(a.pointer == b.pointer)
return false;
multiset<string>::iterator it1 = a.pointer -> begin();
multiset<string>::iterator it2 = b.pointer -> begin();
while(it1 != a.pointer -> end() && it2 != b.pointer -> end())
{
if(*it1 < *it2)
return true;
else if(*it1 > *it2)
return false;
it1++, it2++;
}
}
};
string word_summary(string & word)
{
char str[27];
for(int i=0; i<26; i++)
str[i] = '0';
str[26] = '\0';
for(int i=0; i<word.size(); i++)
str[word[i]-'a'] ++;
return string(str);
}
map<string, multiset<string> * > anagram_map;
typedef map<string, multiset<string> * >::iterator map_iterator;
void add_word(string & word)
{
string str = word_summary(word);
map_iterator it = anagram_map.find(str);
if(it == anagram_map.end())
{
multiset<string> * tmp = new multiset<string>();
tmp -> insert(word);
anagram_map.insert(make_pair(str, tmp));
}
else
{
multiset<string> * tmp = it -> second;
tmp -> insert(word);
}
}
void get_res()
{
vector<Node> node_vec(anagram_map.size());
int i = 0;
for(map_iterator it = anagram_map.begin(); it != anagram_map.end(); ++ it)
{
node_vec[i].size = it -> second -> size();
node_vec[i].pointer = it -> second;
i ++;
}
sort(node_vec.begin(), node_vec.end(), greater_size());
i=0;
while(i < 5 && i < node_vec.size())
{
cout << "Group of size " << node_vec[i].size << ": ";
multiset<string> * tmp = node_vec[i].pointer;
multiset<string>::iterator it = tmp -> begin();
cout << *it << " ";
multiset<string>::iterator prev = it;
it ++;
for( ;it != tmp -> end(); ++ it)
{
if(*it != *prev)
{
cout << *it << " ";
prev = it;
}
}
cout << "." << endl;
i ++;
}
}
int main()
{
string word;
while(cin >> word)
{
add_word(word);
}
get_res();
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator