Keresés

Új hozzászólás Aktív témák

  • mgoogyi

    senior tag

    válasz Ron Swanson #4172 üzenetére

    Melyik része nem sikerül?
    A megértés?

    Amit linkelt Drizzt fórumtárs, az pont ezt oldja meg:

    #include<iostream>
    #include<algorithm>
    using namespace std;

    void findMaxGuests(int arrl[], int exit[], int n)
    {
    // Sort arrival and exit arrays
    sort(arrl, arrl+n);
    sort(exit, exit+n);

    // guests_in indicates number of guests at a time
    int guests_in = 1, max_guests = 1, time = arrl[0];
    int i = 1, j = 0;

    // Similar to merge in merge sort to process
    // all events in sorted order
    while (i < n && j < n)
    {
    // If next event in sorted order is arrival,
    // increment count of guests
    if (arrl[i] <= exit[j])
    {
    guests_in++;

    // Update max_guests if needed
    if (guests_in > max_guests)
    {
    max_guests = guests_in;
    time = arrl[i];
    }
    i++; //increment index of arrival array
    }
    else // If event is exit, decrement count
    { // of guests.
    guests_in--;
    j++;
    }
    }

    cout << "Maximum Number of Guests = " << max_guests
    << " at time " << time;
    }

    Az int arrl[] az érkezési időpontok tömbje, a int exit[] pedig a távozási időpontok tömbbje.

    Ez rendezi le neked ezt a két tömböt gyorsrendezéssel O(N*logN) időben:

    sort(arrl, arrl+n);
    sort(exit, exit+n);

    A while ciklus pedig végigmegy a két tömbbön úgy, hogy hol az egyiket lépteti, hol a másikat.
    Az"i" az érkezés indexe, a "j" a távozásé.

    Annyi, hogy ennek a programnak a kimenete az, hogy melyik időpontban voltak a legtöbben és nem az, hogy melyik vendég találkozott a legtöbb másikkal, de a két probléma technikailag szinte azonos.

    Ha valami nem világos, kérdezz.
    Az eredeti kódoddal a legfőbb baj, hogy volt benne egy egymásba ágyazott for ciklus pár, ami N darab vendég esetén N*N-nel arányos mennyiségű műveletet végez. Ezt hívják O(n^2)-nek és emiatt van az, hogy nagy N-re már túl sok ideig fut a programod. Ugye N=10-nél a a valahány 100 művelet nem gáz, de N=1000-nél már valahány millióról beszélünk.

Új hozzászólás Aktív témák