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