MWPZ06H - Konkurs pseudomatematyczny

Question

Cześć, mam problem napisałem program który u mnie śmiga jak należy ale spoj go nie przyjmuje, wie ktoś może dla czego? Zadanie: https://pl.spoj.com/problems/MWPZ06H/ Mój kod:

#include <iostream>

using namespace std;
int ile;
int maximum=0;
void sortowanie_babelkowe(int *tab, int n)
{
    for (int i=1; i<n; i++)
    {
        for (int j=n-1; j>=1; j--)
        {
            if (tab[j]<tab[j-1])
            {
                int bufor;
                bufor=tab[j-1];
                tab[j-1]=tab[j];
                tab[j]=bufor;
            }
        }
    }
}
        int main()
        {
            cin>>ile;
            for (int i=0; i<ile; i++)
            {
                int ile2;
                cin>>ile2;
                int *pkt=new int [ile2];
                for(int j=0; j<ile2; j++)
                {
                    cin>>pkt[j];
                    if(pkt[j]>maximum)
                        maximum=pkt[j];
                }
                int ilosc=0;
                for(int j=0; j<ile2; j++)
                {

                    if(pkt[j]==maximum)
                        ilosc++;

                }
                for(int i=0; i<ilosc; i++)cout<<maximum<<" ";
                sortowanie_babelkowe(pkt, ile2);
                ile2=ile2-ilosc;
                for(int j=0; j<ile2; j++)
                {
                    cout<<pkt[j]<<" ";
                }
                cout<<endl;
            }
            return 0;
    }

 

Comments

Twoje sortowanie bąbelkowe nie jest do konca zoptymalizowane. Ulepsz algorytm. Złożoność bubbleSort to O(n^2/2)

Answer 1

Przed każdym liczeniem maksimum powinieneś zerować zmienną maximum (albo przenieść jej definicję właśnie do ciała pętli). Tyle.

Możesz się zastanowić nad optymalizacją sortowania czy szukania maksimum. Po sortowaniu max będzie na końcu tablicy i nie będziesz musiał przeszukiwać jej całej ponownie w poszukiwaniu ich ilości. Zapoznaj się z gotowymi funkcjami np sortowania, szukania największych liczb itp.