SPOJ Zliczanie wystąpień

0

Próbuję rozwiązać zadanie na SPOJ-u (http://pl.spoj.pl/problems/KC004/) próbuję różnych technik zadanie wprawdzie wychodzi, ale nie mogę zejść poniżej 1,5 sek. Prawdopodobnie algorytmy które wymyślam nie są optymalne. Proszę o naprowadzenie na rozwiązanie - jedna z wersji kodu wygląda tak:


#include <iostream>
using namespace std;

void zliczaj (int x){
    int ile, c, licznik;
    licznik=0;
    cin>>ile;
    do {
        cin>>c;
        if (c==x)licznik++;
    } while (--ile);
    cout<<"\n"<<licznik;
}

int main()
{
    int x;

    while (cin>>x) zliczaj(x);

    return 0;
}

Nie chodzi mi o gotowe rozwiązanie, ale o naprowadzenie na odpowiedni tok myślenia. Dzięki.

2

Na początku main daj ios::sync_with_stdio(0); - to przyspieszy wczytywanie. Poza przyspieszeniem wczytywania nic lepszego nie wymyślisz. Złożoność tego masz O(n) i niżej nie zejdziesz

0

faktycznie to działa, z 1,5sek spadło na 0,65. Najlepsi mają poniżej 0,1 - wiem, że takie "ściganie" jest głupie. Ale zastanawia mnie, jak można taki wynik osiągnąć?!

0

możesz zamiast iostream korzystać z cstdio - scanf, printf itp.

0

Dzięki za pomoc, widzę że tak głębokie optymalizowanie kodu nie ma sensu. Zastanowiły mnie te różnice w szybkości wykonywania programu. Już się obawiałem, że mam problem w opracowaniu tak prostego algorytmu. :) Jeszcze raz dzięki.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0