Optymalizacja programu

Question

Witam, chciałem rozwiązać zadanie http://main.edu.pl/pl/archive/ilocamp/2010/wie

Jestem początkującym "programistą", dlatego o pomoc z optymalizacją mojego kodu muszę prosić Was. Przez czas nie dostaję za nie maxa punktów. Myślę, że maksymalnie zoptymalizowałem już wpisywanie danych i wypisywanie wyników, pozbyłem się też niepotrzebnych pętli i instrukcji warunkowych... Jednak wciąż jest to za mało. Z góry dziękuję za pomoc. Kod:

 

#include <iostream>
#include <stdio.h>

using namespace std;

int s, l, wynik;
int wys[1000000], wl[100000];

int main()
{
    ios_base::sync_with_stdio(0);

    scanf ("%d", &s);
    scanf ("%d", &l);

    for (int i=0; i<s; i++)
        scanf ("%d", &wys[i]);

    for (int i=0; i<l; i++)
        scanf ("%d", &wl[i]);

    for (int i=0; i<l; i++)
    {
        wynik=0;
        for (int j=0; j<s; j++)
        {
            if (wl[i]>wys[j])
                wynik++;
            else
            {

                break;
            }

        }
        printf(" %d", wynik);
    }
    return 0;
}

 

Answer 1

A ile punktów za to dostajesz?

To na pewno wina czasu działania? Może musisz wyzerować te tablice bo w c++ są często jakieś śmieci. Możesz też zamiast tych tablic użyć klasy map.

Jedyne co mi przychodzi do głowy to zapisanie pozycji i wysokości najwyższego stopnia i jeże li coś go przekroczy to nie trzeba sprawdzać dalej bo wiadomo że kolejne są niższe. Albo nawet inaczej zapisanie dla każdej po kolei wartości ile bezpośrednio po niej ma mniejszą wartość, aby móc je przeskoczyć.

Comments

Dostaje jakieś 70 punktów i piszą przekroczenie czasu. Nie mam pojęcia co mam z tym zrobić, bo przecież pętla jest przerywana w momencie gdy znajdzie sie większy niż mieszkaniec schodek.

---

Moim zdaniem robienie minimalnych optymalizacji kosztem brudnego kodu to gówno a nie programowanie i uczy złych nawyków.

Musisz wykombinować jakieś optymalizacje np. jak ktoś 2 ludzi ma wysokość 123123 to nie liczyć na nowo wszystkich schodów tylko gdzieś zapisać że dla takiej wysokości tyle a tyle schodów się przejdzie.

Innym pomysłem może być zapisywanie przy czytaniu schodów ile schodów po danym schodzie jest niższych i potem jak ktoś ten schód przejdzie to przeskoczy te niższe i doda mu się od razu odpowiednia liczba.

Pokombinuj po prostu, albo rzuć to i napisz jakąś grę :D

---

W tym momencie to wolałbym rzucić to i otworzyć punkt sprzedaży części do Poloneza :p

 

Myślałem żeby zrobić to zupełnie inaczej, bo przecież jest możliwość posortowania schodków i potem wyszukiwania który schodek jest ostatnim mniejszym od człowieka, ale na razie nie chce tego robić, bo chcę się czegoś nauczyć. Tak sobie to tłumaczę. Z resztą, na moim poziomie to bym to z tydzień robił zanim bym wbił na 100. Mam nadzieję na jakiś magiczny pomysł jak skrócić czas działania tego programu, ale na razie na nic nie wpadłem.

---

Podałem Ci 2 sposoby w poprzednim komentarzu, ten pierwszy jest prosty i powinienem dać radę go zrobić. To posortowanie schodków chyba najlepsze nie jest, bo jak ktoś da radę jest wyższy np. od 1 i 3 to wynikiem powinno być 1 bo od 2 jest niższy i nie wejdzie na 3.