834. Imiona

[przemek625]

Witam, niestety mój kod nie jest akceptowany przez Spoja(pomimo, że przykładowy input z treści zadania daje poprawny output). W skrócie mój program:

pobiera dane, wybiera imię i zamienia wszystkie litery na duże. Następnie wsadza to wsyzstko do mapy, która zalicza ilość wystąpień elementu. Potem kopiuję całą mapę do wektora(tak wiem, pewnie dałoby sie lepiej, ale jakoś to mi przyszło do głowy), który sortuję wzgledem liczby wystąpień. Tak posortowane dane wyświetlam.

#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;
//wsadzamy imię do mapy, jak się powtorzy to zwiekszamy drugi parametr o 1
        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;
         }






    }

[narbej]

Wyświetlane wiersze powinny być posortowane według malejącej liczby wystąpień, a przy remisach według porządku alfabetycznego imion

[przemek625]

No i wydaje mi się, że tak robi mój program Widzisz może gdzieś błąd w kodzie :(?

[narbej]

Błąd jest malutki i subtelny. Zakładasz, że sortowanie wg imion, "załatwiane" jest przez mapę. I rzeczywiście, tak jest, to prawda. Potem, po przepisaniu do wektora sortujesz wg ilości oraz zakładasz, że kolejność, "ustawiona" mapą, przy takiej samej ilości wystąpień zostanie nie zmieniona? Dla małych testów, wygląda ok, ale dla dużych...?
W takim wypadku, należało by:
1. Trochę inaczej napisać algorytm.
2. Uzupełnić funkcję porównującą left > right
3. Użyć innego sortowania, zachowującego "porządek" np: http://www.cplusplus.com/reference/algorithm/stable_sort/

[przemek625]

Działa Tylko czas marny 1.38, a widzę, że niekórzy osiagają blisko 0. Co należałoby poprawić w tym rozwiązaniu?

Dodatkowo chciałbym Ci narbej podziękować za pomoc, którą mi już niejednokrotnie udzieliłeś :)!

[narbej]

Zamiast podziękowań wystarczyłby jakiś mały browarek a jak nie to chociaż jakieś małe like this post
Do 0.0 daleko. Na początek możesz dodać:

main(){
    ios_base::sync_with_stdio(0);
    .....

Lub użyć innych szybszych metod wczytywania. Użyć tablic char zamiast stringów, Sam mam słaby czas, więc nie wiem. Może zrezygnować z map na rzecz tylko wektora?

No i poprawki bardziej estetyczne:
Zamiast:

 for(int i=0;i<imie.length();i++)
            {
                if(imie[i] >90)
                {
                    imie[i]=imie[i]-32;
                }

Moim zdaniem lepiej:

 for (int i = 0; i < imie.length(); i++)
            {
                if (imie[i] > 'Z')
                     imie[i] = imie[i] - ('a' - 'A');

A jeszcze prościej [ale może wolniej]:

 for (int i = 0; i < imie.length(); i++)
                imie[i] = toupper(imie[i]);