Moje rozwiązanie nie zalicza czasowo ostatniego testu.Dany jest zbiór \(\displaystyle{ A}\) złożony z \(\displaystyle{ n}\) liczb naturalnych. Mając liczbę naturalną \(\displaystyle{ i}\) wyznacz, ile jest w zbiorze A liczb od niej mniejszych.WejścieW pierwszym wierszu podana jest liczba \(\displaystyle{ n<10^6}\) , czyli moc zbioru \(\displaystyle{ A}\). Następnie kolejne \(\displaystyle{ n}\) wierszy zawiera elementy \(\displaystyle{ A}\). Są to liczby naturalne z zakresu \(\displaystyle{ [1..10^{30}-1]}\)
Następnie podana jest liczba \(\displaystyle{ k<10^6}\) oraz w kolejnych \(\displaystyle{ k}\) wierszach podawane są liczby naturalne \(\displaystyle{ i_1,..., i_k}\) z zakresu \(\displaystyle{ [1..10^{30}-1]}\).WyjścieDla każdej liczby \(\displaystyle{ i_s}\) należy podać ile elementów w zbiorze A jest mniejszych od \(\displaystyle{ i_s}\).
Kod programu w C++.
Ukryta treść:
Liczby wczytuję jako ciągi znaków.
Stworzyłem sobie 'dynamiczną tablicę' (vector) 30 'dynamicznych tablic' stringów (ciągów znaków). Każda wewnętrzna tablica przechowuje stringi o danej długości od 1 do 30. Po wczytaniu i wrzuceniu w odpowiednie miejsce następuje sortowanie w wewnętrznych tablicach.
Przy zliczaniu dodaję sumuję rozmiary (ilość elementów) tablic przechowujących stringi o mniejszej długości, a później zliczam elementy z tablicy o danej długości.
Tak wygląda moje podejście do tego problemu. Jak mogę to zrobić optymalniej Jakie zastosować struktury Wszelkie porady mile widziane.