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

• #4173 mgoogyi senior tag Ron Swanson #4172

  Új Válasz 2018-11-22 08:44:50 #4173

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  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