Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:用map<string, multiset<string> * > 以及stl sort,297ms过。

Posted by 2007011268 at 2012-08-08 23:18:14 on Problem 2408
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator