[es] - jedan kratak zadatak

SuPeR_MaSteR
Marko Stamenković

Član broj: 88590
Poruke: 115
*.inffo.net.

Profil

^{23.12.2006. u 15:08 - pre 236 meseci}

Imam jedan zadatak:
Potrebno je ucitati N (0 < N <= 10000) brojeva koji u zadatku predstavljaju broj "ljudi" a zatim u narednih N linija nalaze se dva broja A[j] i B[j], gde A[j] prestavlja interval u opsegu [1..1000000] kada je osoba dosla na "zurku" a B[j] interval kada je osoba otisla za zurke.
Na standardni izlaz ispisati jedan broj, maksimalan broj ljudi koji je u istom intervalu (trenutku) bio na zurci.
Vremensko Ogranicenje : 1 sekunda

E sad, ja sam to resio tako sto sam medju ulaznim vrednostima prvo pronasao minimalni i maximalni element, i oni predstavljaju uslov izvrsavanja petlje,tj. ponavljanje petlje se izvrsava dok je max > min. A zatim deklarisao sam dva brojaca: prvi se inkrementira u slucaju da je (i >= a[j] and i <= b[j]) uslov ispunjen, to jest ako je trenutna vrednost u intervalu a[j] i b[j], a zatim se u drugom brojacu pamti najveca vrednost prvog brojaca kako bi se znao najveci broj ljudi koji je bio prisutan u istom trenutku.
Evo kod:

Code:

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n],b[n];
    int min,max;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
        if (i == 0)
            min = a[0],max = b[0];
        else
        {
            if (min > a[i])
               min = a[i];
            if (max < b[i])
               max = b[i];
        }
    }
    int br1 = 0,br2 = 0;
    for (int i = min; i < max; i++,br1 = 0)
    {
        for (int j = 0; j < n; j++)
            if (i >= a[j] and i <= b[j])
                br1++;
        if (br1 > br2)
               br2 = br1;
    }
    cout << br2;
    return 0;
}

Tacna su resenja, ali problem je sto program prelazi vremensko ogranicenje.
Ima li neko ideju kako ovo da se resi na drugaciji nacin, tako da se kod optimizuje??

Odgovor na temu

Milos Stojanovic
Belgrade

Član broj: 10343
Poruke: 1864
*.adsl.beotel.net.

ICQ: 282954730
Sajt: www.sietf.org

+7 Profil

Re: jedan kratak zadatak - help

^{28.12.2006. u 23:53 - pre 236 meseci}

Tebe u principu ne zanima ko je izašao a ko je ušao, zanima te samo da se taj događaj desio.

Prvo sortiraš oba niza, recimo qsortom - složenost O(n log n), zatim jednim prolazom kroz oba niza brojiš koliko je ljudi ušlo a da u međuvremenu niko nije izašao i uvećavaš brojač, i obrnuto, brojiš koliko je izašlo i smanjuješ brojač, nakom svakog uvećanja proveriš da li je to novi maximum, i završavaš kada oba niza stignu do kraja, tj. još bolje kada niz dolazaka stigne do kraja, jer nas na dalje više ništa ne zanima.
Složenost ovog drugog dela je O(n), što znači da je ukupna složenost O(n logn), što bi trebalo da bude dosta ispod sekunde za N < 10000

Evo koda otprilike, napamet:

Code:
...

long dosao[10000];
long otisao[10000];
int n;
...

int max_u_intervalu()
{
    // ucitaj n
    // ucitaj niz dosao
    // ucitaj niz otisao

    // sortiraj(dosao, n);
    // sortiraj(otisao, n);

    int max = 0;
    int c = 0;
    int d = 0, o = 0;

    while(d < n)
    {
        if(o < n)
        while(dosao[d] <= otisao[o])
        {
            c++; d++;
            if(d == n) break;
        }
        else break;

        if(c > max) max = c;

        if(d < n)
        while(dosao[d] > otisao[o])
        {
            c--; o++;
            if(o == n)
            {
                c += n-d
                if(c > max) max = c;
                break;
            }
        }
    }

    return max;
}

_{[Ovu poruku je menjao trooper dana 29.12.2006. u 01:03 GMT+1]}

ex. trooper
Oh goody... it's my Illudium PU-36 Explosive Space Modulator!
Softversko Inženjerstvo
♪♫♪

Odgovor na temu