Zadanie z main mijanka
Ostatnio zmodyfikowano 2017-06-03 18:35
badyl94 Temat założony przez niniejszego użytkownika |
Zadanie z main mijanka » 2017-06-03 14:46:26 Hej pracuje nad zadaniem z main'a https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/mij/Wszystko niby jest ok ale działa za wolno ma ktoś pomysł jak ten algorytm przyspieszyć? #include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int tab[ n ];
for( int i = 0; i < n; i++ ) cin >> tab[ i ];
int wynik = 0;
for( int i = 0; i < n; i++ )
{
for( int j = i; j < n; j++ )
{
if( tab[ i ] < tab[ j ] ) wynik++;
}
}
cout << wynik;
return 0;
}
|
|
pekfos |
» 2017-06-03 15:37:18 Użyj innego algorytmu. Po to jest limit czasu, żeby nie dało się użyć podejścia naiwnego. |
|
michal11 |
» 2017-06-03 15:40:17 Wczytuj liczby po kolei, przy każdej wczytanej jedynce dodawaj do wyniku liczbę dotychczas wczytanych zer. Czyli w zasadzie potrzebujesz tylko 2 intów i jeden pętli |
|
badyl94 Temat założony przez niniejszego użytkownika |
» 2017-06-03 17:42:00 Zrobiłem "chyba" tak jak pisał michal11 #include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int tab[ n ];
int wynikZero = 0, wynik = 0;
for( int i = 0; i < n; i++ ) cin >> tab[ i ];
for( int i = 0; i < n; i++ )
{
if( tab[ i ] < 1 ) wynikZero++;
if( tab[ i ] > 0 ) wynik = wynik + wynikZero;
}
cout << wynik;
return 0;
}
wyrzuca mi cos takiego na sprawdzarce 4 wiersz 1: wczytano '-2037444346', a oczekiwano '122516607238' 5 wiersz 1: wczytano '1035931238', a oczekiwano '26805735014' 6 wiersz 1: wczytano '420698446', a oczekiwano '124974750030' 8 wiersz 1: wczytano '-1739176257', a oczekiwano '148584679103' 9 wiersz 1: wczytano '214640261', a oczekiwano '124768691845' |
|
Monika90 |
» 2017-06-03 18:10:26 Zrezygnuj z tablicy i użyj typu long long do zliczania samochodów. |
|
Chowan |
» 2017-06-03 18:11:38 z tego co się doczytałem to @michal11 proponował zrobić wszystko w jednej pętli #include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int tab[ n ];
int wynikZero = 0, wynik = 0;
for( int i = 0; i < n; i++ ) {
cin >> tab[ i ];
if( tab[ i ] == 0 ) wynikZero++;
if( tab[ i ] == 1 ) wynik += wynikZero; }
cout << wynik;
return 0;
}
|
|
Kinexity |
» 2017-06-03 18:15:39 Jeżeli dobrze rozumiem zadanie to taki kod powinien zadziałać: #include <iostream>
using namespace std;
int main()
{
unsigned long long n, r, lw = 0, wynik = 0;
cin >> n;
for( unsigned long long i = 0; i < n; i++ ) {
cin >> r;
if( r == 0 ) {
++lw;
continue;
}
wynik += lw;
}
cout << wynik << endl;
return 0;
}
|
|
badyl94 Temat założony przez niniejszego użytkownika |
» 2017-06-03 18:35:22 Dzięki pomogło :)
Rzeczywiście tablice są tu nie potrzebne Dzięki jeszcze raz |
|
| « 1 » |