Új hozzászólás Aktív témák

• D@ve89 tag

  #4048 2009-11-07 13:01:40

  Új Válasz

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  

  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 50

  Ezen 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