- Hálózati / IP kamera
- DIGI internet
- ASUS routerek
- Kaspersky Antivirus és Internet Security Fórum
- Sorra osztja a dollármilliárdokat az USA a chipgyártóknak
- Kanada big tech-adót zúdít az amerikai cégek nyakába
- Alternatív kriptopénzek, altcoinok bányászata
- Milyen routert?
- DIGI kábel TV
- WLAN, WiFi, vezeték nélküli hálózat
-
IT café
Új hozzászólás Aktív témák
-
D@ve89
tag
Sziasztok!
Volna egy feladatom, de nem tudok rájönni a helyes algoritmusra. Ebben kérném segítségeteket. A feladat szövege:
Adott a számegyenesen egy szakasz az A és B egész értékű végpontjával (A < B), és adottak a [k1; v1]; ... ; [kn; vn] (ki < vi; i = 1; ... ; n) zárt intervallumok egész értékű kezdő és végpontjaikkal. Kiválasztandó az intervallumoknak egy olyan halmaza, amely lefedi az [A;B] szakaszt, azaz minden x egész számra, amely eleme az [A;B] szakasznak (A <= x <= B) van olyan kiválasztott [ki; vi] intervallum, amelynek x eleme, azaz ki <= x <= vi. Az a cél, hogy a lefedés költsége, ami a kiválasztott intervallumok hosszainak összege, minimális legyen. Egy [k; v] intervallum hosszán a v-k értéket értjük. Írjon olyan programot, amely megad egy minimális költségű lefedést!
Bemeneti speci�káció
A be.txt szöveges állomány első sora két egész számot tartalmaz (egy szóközzel elválasztva), a lefedendő szakasz. A kezdő és B végpontját (1 <= A < B <= 10000). A második sor egyetlen egész számot, a lefedésre használható intervallumok n (1 <= n <= 1000) számát tartalmazza. A következő n sor mindegyike két egész számot tartalmaz: k v, egy lefedésre használható intervallum k kezdő és v végpontját (A <= k < v <= B). A bemenetben az
intervallumok a jobb-végpontjuk (v) szerint nemcsökkenő sorrendben vannak megadva./ki, vi jelöléseknél az "i" az indexet jelöli/
Példa a be.txt-re:
2 50
6
2 4
3 18
15 19
10 33
20 45
22 50Ezen felül meg van adva az időlimit (0,1 mp), és a memórialimit (16MB).
Szóval kellene valami viszonylag gyors algoritmus.
Az én ötletem (ami nem feltétlen a minimális költségű lefedést adja meg):
Ugyebár a megadott intervallumok végpont szerint nemcsökkenő sorrendben vannak megadva. Az első és utolsó intervallumra mindenképpen szükségünk lesz. Vesszük az utolsó intervallumot. Majd haladunk visszafele, és megnézzük, hogy az előtte levő intervallum végpontja >= az utolsó intervallum kezdőpontjánál. Ha igen, akkor eltároljuk, és haladunk tovább az intervallumokkal, megnézzük ugyanezt a vizsgálatot az a következőnél is. Ha végig értünk, akkor kiválasztjuk a leghosszabb intervallumot a megfelelőek közül, majd ezt vesszük "utolsónak", és kezdjük elölről az egészet.
Mindaddig csináljuk ezt az egészet, míg az első intervallum nem lesz a mi "utolsónk".Viszont ez nem a minimális költségű lefedést adja, hanem a legnagyobb intervallumokkal fedi le a szakaszunkat.
Tehát ezt kéne kombinálni még úgy, hogy az intervallumok átfedéseinek összege minimális legyen.
Kódra nincs szükségem, ha meglenne az algoritmus, az már valószínűleg menne.
Előre is köszi.
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
- Rog Strix PC - i7 7700k, 32Gb RAM, GTX 1080 8Gb, 2x 512 M2, 3TB HDD, Wifi stb.
- Canon PowerShot SX50 HS 12,1 megapixeles ultrazoom fényképezőgép
- Keychron K2 HUN + táska
- Eladó GIGABYTE GTX 1060 3gb OC Verzió!
- Lenovo Thinkpad X230i, 12,5" HD Kijelző, I3-3120M CPU, 8GB DDR3, 128GB SSD, WIN 10, Számla, Garancia