Asahel Temat założony przez niniejszego użytkownika |
Sortowanie mapy » 2015-10-04 15:29:17 Witam, rozwiązuję zadanie: http://pl.spoj.com/problems/NAMES/. Zastanawiam się jak posortować mapę względem drugiej współrzędnej tj. liczba wystąpień imienia w wprowadzanych stringu. #include <iostream>
#include<string>
#include<map>
using namespace std;
int main()
{
string nr, nazwisko, imie;
map < string, int > osoba;
while( cin >> nr >> nazwisko >> imie )
{
for( int i = 0; i < imie.length(); i++ )
{
if( imie[ i ] >= 97 && imie[ i ] <= 122 )
{
imie[ i ] = imie[ i ] - 32;
}
}
++osoba[ imie ];
}
for( map < string, int >::const_iterator it = osoba.begin();
it != osoba.end(); ++it )
{
cout << it->first << "\t" << it->second << endl;
}
}
|
|
pekfos |
» 2015-10-04 18:05:26 Skopiuj dane do innej struktury danych, np wektora par. |
|
Asahel Temat założony przez niniejszego użytkownika |
» 2015-10-04 21:54:38 Tak zrobiłem. Program wygląda jak niżej. Niestety spoj nie akaceptuje tego rozwiązania! Pomimo, że przykładowy inpout z treści zadania daje identyczny output jak w treści :( No i czas wykonania też jest przerażający :( #include <iostream>
#include<string>
#include<map>
#include<vector>
#include <algorithm>
using namespace std;
typedef std::pair < string, int > my_pair;
bool sort_pred( const my_pair & left, const my_pair & right )
{
return left.second > right.second;
}
int main()
{
string nr, nazwisko, imie;
map < string, int > osoba;
vector < my_pair > data;
while( cin >> nr >> nazwisko >> imie )
{
for( int i = 0; i < imie.length(); i++ )
{
if( imie[ i ] > 90 )
{
imie[ i ] = imie[ i ] - 32;
}
}
++osoba[ imie ];
}
for( map < string, int >::const_iterator it = osoba.begin(); it != osoba.end(); ++it )
{
data.push_back( make_pair( it->first, it->second ) );
}
sort( data.begin(), data.end(), sort_pred );
for( int i = 0; i < data.size(); i++ )
{
cout << data[ i ].first << " " << data[ i ].second << endl;
}
}
|
|
michal11 |
» 2015-10-04 23:02:28 |
|
Monika90 |
» 2015-10-04 23:55:19 sortowanie jest niestabilne, zamień sort na stable_sort i zobacz czy przejdzie. Albo zostaw sort, ale zmień predykat na bool sort_pred( const my_pair & left, const my_pair & right )
{
return left.second > right.second || left.second == right.second && left.first < right.first;
}
i powiedz nam która wersja działa szybciej. |
|
carlosmay |
» 2015-10-05 05:23:24 map < string, int >::const_iterator itr_end = osoba.end();
for( map < string, int >::const_iterator it = osoba.begin(); it != itr_end; ++it ) Może to coś przyspieszy. |
|
Asahel Temat założony przez niniejszego użytkownika |
» 2015-10-05 22:43:48 Dziękuję za odpowiedzi. Zamieniłem sort na stable_sort i program został zaakceptowany przez spoja. Jedynym problem pozostaje wydajność, którą należy dopracować. Jestem bardzo ciekawy z czego korzystały osoby, które osiągnęły czasy bliskie 0.00. Jakieś pomysły? |
|
withelm |
» 2015-10-09 13:46:30 Jednym z szybszych rozwiązań jest np to:
1. Tworzysz sobie puste drzewo TRIE(https://pl.wikipedia.org/wiki/Drzewo_trie).
2. Dodajesz każde imię(małe znaki zamieniasz na wielki) w tym drzewie i w przypadku gdy kończy się dane imię to:
a) ustawiasz flagę, że to koniec imienia
b) dodajesz +1 do licznika wystąpień tego konkretnego imienia
3. Odczytujesz wynik DFS i w przypadku gdy widzisz zaznaczoną flagę wypisujesz imie + licznik wystąpień.
gdzie n to suma znaków imion
Całkowita złożoność tego rozwiązania to O(n)
Twoje jest wolne ponieważ ma O(n log(n)). Dodatkowo korzystasz z mapy która jest wolna do tego typu zadań.
Plus na spoju stosuje się sztuczki, z szybkim wczytywaniem (http://ftp.tuwien.ac.at/languages/c/programming-bbrown/c_075.htm) |
|
| « 1 » |