AL_01_02 - Kolejka - Przekroczono limit czasu
Ostatnio zmodyfikowano 2023-01-13 20:56
Ash Temat założony przez niniejszego użytkownika |
AL_01_02 - Kolejka - Przekroczono limit czasu » 2023-01-12 21:05:57 Co można zmienić aby nie było tego błędu? Treść zadania: https://pl.spoj.com/problems/AL_01_02/ #include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio( 0 );
cin.tie( 0 );
int ile_testow;
char naj_znak;
string ciag;
cin >> ile_testow;
for( int i = 1; i <= ile_testow; i++ ) {
cin >> ciag;
naj_znak = ciag[ ciag.size() - 1 ];
for( int j = ciag.size() - 1; j >= 0; j-- ) {
if( naj_znak > ciag[ j ] ) {
ciag.erase( j, 1 );
}
naj_znak = ciag[ j ];
}
cout << ciag << endl;
}
return 0;
} |
|
pekfos |
» 2023-01-12 21:34:08 Nie modyfikuj tak napisu. Usuwanie znaku z początku ma złożoność liniową, więc ryzykujesz kwadratową na całej pętli. |
|
Ash Temat założony przez niniejszego użytkownika |
» 2023-01-12 21:45:21 A chociaż ten będzie lepszy od pierwszego? #include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio( 0 );
cin.tie( 0 );
int ile_testow;
char naj_znak;
stack < char > kolejka;
string ciag;
cin >> ile_testow;
for( int i = 1; i <= ile_testow; i++ ) {
cin >> ciag;
naj_znak = ciag[ ciag.size() - 1 ];
for( int j = ciag.size(); j >= 0; j-- ) {
if( naj_znak <= ciag[ j ] ) {
naj_znak = ciag[ j ];
kolejka.push( naj_znak );
}
}
while( kolejka.empty() == 0 ) {
cout << kolejka.top();
kolejka.pop();
}
cout << endl;
}
return 0;
}
|
|
pekfos |
» 2023-01-12 21:59:09 Po co tak kombinujesz z przetwarzaniem od końca? Dużo prościej byłoby od początku i konstruować drugi std::string. |
|
Ash Temat założony przez niniejszego użytkownika |
» 2023-01-13 16:03:23 Czyli musiałbym zmienić aby było "j++" zamiast "j--" (zmieniając całego for'a)? |
|
pekfos |
» 2023-01-13 20:56:44 Można to zmienić na j++ bez zmiany zachowania programu, przywiązujesz znaczenie do dziwnych szczegółów.. Zaimplementuj to dosłownie tak jak jest napisane w zadaniu. String opisuje chronologicznie kolejne zdarzenia, więc czemu by ich nie przetwarzać w tej właśnie kolejności? Nie musisz nawet przechowywać go w całości w pamięci. |
|
| « 1 » |