- ricshard444: Fényképező ? Telefon helyett
- ubyegon2: Airfryer XL XXL forrólevegős sütő gyakorlati tanácsok, ötletek, receptek
- Luck Dragon: Asszociációs játék. :)
- sziku69: Fűzzük össze a szavakat :)
- eBay-es kütyük kis pénzért
- gban: Ingyen kellene, de tegnapra
- Meggyi001: Egy olcsó vállfás megoldás a pólóimnak...
- VoidXs: Tényleg minden játék optimalizálatlan?
- sziku69: Szólánc.
- erkxt: A Roidmi becsődölt – és senki nem szól egy szót sem?
Ú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, aint 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
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- Eredeti Windows 10 / 11 Pro aktiválókulcs AZONNALI SZÁLLÍTÁSSAL!
- BESZÁMÍTÁS! MSI B450M R5 5500 16GB DDR4 512GB SSD RTX 2060 Super 8GB Rampage SHIVA ADATA XPG 600W
- Bomba ár! Dell Latitude 5495 - Ryzen 5 I 16GB I 256SSD I 14" FHD I HDMI I Radeon I Cam I W10 I Gari!
- Eredeti Lenovo USB-C 65W töltő
- 18 éve! Billentyűzet magyarítás magyarosítás. Festés vagy lézerezés és egyebek! 3 lehetőség is van.
Állásajánlatok
Cég: Promenade Publishing House Kft.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest