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!
- Meggyi001: Eldugott helyek Párizsban, amiket jó eséllyel még nem láttál...
- sziku69: Fűzzük össze a szavakat :)
- eBay-es kütyük kis pénzért
- Magga: PLEX: multimédia az egész lakásban
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- MasterDeeJay: ASUS Maximus VIII Ranger Z170 6-7-8-9-10 gen támogatás (Coffeetime mod)
- Elektromos rásegítésű kerékpárok
- Luck Dragon: Asszociációs játék. :)
- Sub-ZeRo: Euro Truck Simulator 2 & American Truck Simulator 1 (esetleg 2 majd, ha lesz) :)
- GoodSpeed: Egy bihari a Hajdúságban
-
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!
- Hobby elektronika
- Milyen SSD-t vegyek?
- Androidos fejegységek
- Emelkedik a korábbi generációs Intel CPU-k ára
- Videó stream letöltése
- Nem kamera gomb, kérem, AI-gomb! Kezünkben a Honor Magic8-ak
- A fociról könnyedén, egy baráti társaságban
- Xiaomi 15T - reakció nélkül nincs egyensúly
- Motorola Edge 50 Neo - az egyensúly gyengesége
- Synology NAS
- További aktív témák...
- 2025.10.02 - Frissített lista - Lenovo LOQ / LEGION Pro , Yoga Pro (RTX 4060 / 4070 / 4080 / 4090)
- AKCIÓ! Microsoft Surface 5 13,5 notebook - i5 1235U 8GB RAM 256GB SSD Intel Iris Xe IGP 27% áfa
- GYÖNYÖRŰ iPhone 12 Mini 128GB Green-1 ÉV GARANCIA - Kártyafüggetlen, MS3640
- GYÖNYÖRŰ iPhone 12 64GB Black -1 ÉV GARANCIA - Kártyafüggetlen, MS2113, 100% Akkumulátor
- BESZÁMÍTÁS! MSI B760 WIFI i9 14900KF 32GB DDR5 1TB SSD RTX 3090 Trinity OC 24GB LIAN LI PC-O11D 750W
Állásajánlatok
Cég: NetGo.hu Kft.
Város: Gödöllő
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest