Informatika gyűjtemény

NézetNyomtat

Staféta (Megoldás)
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2009 > Második forduló > 11-13. osztály
Elmélet > Algoritmusok > Mohó
Elmélet > Algoritmusok > Rendezések

Algoritmus

Az algoritmushoz két listára lesz szükségünk: az (list1) egyik tartalmazza a futókat kezdési kilométer alapján növekvő sorrendben, ha egyenlőség van akkor befejezés alapján csökkenőben, a másikba (list2) pedig majd időnként pakolunk futókat, de őket befejezési kilométer alapján csökkenő sorrendben rendezzük majd, ha egyenlőség van akkor kezdés alapján növekvőben. Miért is?
A list1-ből kiválasztjuk az első futót. Ő nyílván a 0. kilométernél kezd, és a lehető legtovább fut azok közül akik a 0. kilométernél kezdik: eddig jók vagyunk. Utána a list1-ből kiválogatjuk azokat a futókat, akiknek a kezdési $z$ kilométerére teljesül, hogy $x\leq z\leq y$, ahol $x\mbox{ és }y$ az első futó kezdési és befejezési kilométere. Őket bepakoljuk list2-be. Nyílván a list2 első elemére teljesül, hogy ő fut a legtovább azok közül akik át tudják venni az első futótól a lángot, és ha több ilyen van, akkor ő az aki a leghamarabb átveheti (ez fontos lehet a többi futó kiválasztásánál). Tehát ő lesz a 2. futó, és ugyanezt folytatjuk azzal a különbséggel, hogy a list1-ben nem a legelejéről indítjuk a keresést, hanem a 2. futó indexétől kezdődően.
A fenti két listát többféle adatszerkezetben el lehet képzelni:
  • Lista: két egyszerű lista, melyet rendezni tudunk a megfelelő kritériumokkal.
  • Prioritási sor: Ez a list2-nél bizonyul hasznosnak ahol tényleg csak a legfontosabb elem kell, nem kell benne utána keresnünk.
Futo objektum attribútumai: x, y, id

list1<Futo> := beolvassuk ide a futókat
list2<Futo> := üres
futok<int> := üres {ő lesz a megoldáshalmaz, ide dobáljuk a futók ID-ját/sorszámát}
kilep := hamis

{ALGORITMUS}

list1.rendezXAlapjánNövekvőbe()
futok.hozzáad( list1[1] ); {az első futó kezdi a futást, biztosan 0-tól fut és a lehető legtovább}
idx := last_idx := 1 {ő az első futó!}

Ciklus amíg nem kilep
    // list[idx] futótól kell átvenni a lángot.
    // az adott indextől kezdve nézzük a futókat, addig ameddig ő még átveheti a lángot
    // őket a list2-ben tároljuk.
    kilep2 := hamis
    Ciklus
        idx++
        Ha idx = list1.hossz Akkor kilep2 := igaz {ha végén járunk, akkor kilépünk}
        Különben
            Ha list1[last_idx].x <= list1[idx].x és list1[idx].x <= list1[last_idx].y Akkor
                {Ha a futó átveheti a lángot, akkor megjegyezzük}
                tmp := list1[idx].másol()
                tmp.id := idx {itteni ID tartalmazza a listben-i id-t!}
                list2.hozzáad(tmp)
            Különben kilep2 := igaz
            Elágazás vége
        Elágazás vége
    amíg nem kilep2

    // ezt a list2-t rendezzük befejezés szerint csökkenőbe -> az a legjobb aki legtovább futja.
    list2.rendezYAlapjánCsökkenőbe()
    last_idx := list2[1].id // ő veszi át a lángot, mert ő tudja a legtovább futni
    futok.hozzáad(list1[last_idx].id) // hozzáadjuk a sorszámát a megoldáshoz.

    // ha az adott futó lefutja a távolságot akkor vége.
    Ha list1[last_idx].y = K Akkor
        kilep := igaz
    Elágazás vége
    idx := last_idx {mostantól tőle később induló futót keresünk}
    list2 := üres {kiürítjük}
Ciklus vége

Megoldások

Kriván Bálint (C#): kb_stafeta.cs