Hirdetés
- ASUS Maximus VIII Ranger Z170 6-7-8-9-10 gen támogatás (Coffeetime mod)
- DFI és DFI Lanparty gyűjteményem
- Möbelix Milan íróasztal - a tapasztalatok összeszerelés után
- Keychron V6 Max (HU) Mechanikus vezetéknélküli billentyűzet (Bluetooth, RF, USB)
- Újjászületés: szombattól új szerverkörnyezetben a PROHARDVER!
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- sziku69: Fűzzük össze a szavakat :)
- Luck Dragon: Asszociációs játék. :)
- MasterDeeJay: ASUS Maximus VIII Ranger Z170 6-7-8-9-10 gen támogatás (Coffeetime mod)
- GoodSpeed: Egy bihari a Hajdúságban
- Magga: PLEX: multimédia az egész lakásban
- Doky586: Torrent beállítás kezdőknek
- f(x)=exp(x): A laposföld elmebaj: Vissza a jövőbe!
- sellerbuyer: Az RGB LED TV leváltja az OLED-et?
- gerner1
-
LOGOUT
Ú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!
- Samsung Galaxy Watch4 és Watch4 Classic - próbawearzió
- Fujifilm X
- Arc Raiders
- Battlefield 6
- Audi, Cupra, Seat, Skoda, Volkswagen topik
- Formula-1
- Samsung Galaxy S23 és S23+ - ami belül van, az számít igazán
- Kaspersky Antivirus és Internet Security Fórum
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- MOBILTELEFON / TARTOZÉK / OKOSÓRA / OKOS KIEGÉSZÍTŐ beárazás
- További aktív témák...
- ASUS VivoBook Go 15 (X1504ZA) 15.6"FHD IPS-Intel i7-1255U-8GB DDR4 Ram-512GB SSD-Iris Xe Graphics!
- AKCIÓ!!! RITKASÁG! Microsoft Surface Pro 11 Qualcomm Snapdragon X Elite 16GB 512GB OLED 120Hz Gar!
- AKCIÓ!!! RITKASÁG! Microsoft Surface Pro 11 Qualcomm Snapdragon X Elite 16GB 1000GB OLED 120Hz Gar!
- Acer Aspire 5 +2 év garanciával, i5-12350H/RTX2050/512GB SSD/16GB Ram
- Xbox Series X 2 kontrollerel töltő
- GYÖNYÖRŰ iPhone 11 64GB Black -1 ÉV GARANCIA - Kártyafüggetlen, MS3347, 100% Akksi
- GYÖNYÖRŰ iPhone 11 Pro 256GB Midnight Green -1 ÉV GARANCIA -Kártyafüggetlen, MS3370,94% Akkumulátor
- 136 - Lenovo Legion Pro 7 (16IRX9H) - Intel Core i9-14900HX, RTX 4080 - 4 ÉV GARANCIA!
- Gamer PC-Számítógép! Csere-Beszámítás! I5 12400F / RTX 3070 8GB / 32GB DDR4 / 1TB SSD
- ÁRGARANCIA! Épített KomPhone Ultra 9 285K 32/64GB RAM RX 9070 XT 16GB GAMER PC termékbeszámítással
Állásajánlatok
Cég: Promenade Publishing House Kft.
Város: Budapest
Cég: NetGo.hu Kft.
Város: Gödöllő