C++ szöveges feladat?
Józsikának van "A" és "B" kupac fánkja, ezekben "n" és "m" darab fánk.
"X" perc múlva haza ér Józsika apja és mivel megenné az összeset, ezért Józsika minél több darabot meg akar enni az érkezéséig.
A fánkok különböző méretűek és Józsikának "A₁","A₂"..."Aₙ" és "B₁","B₂"..."Bₘ" percig tart megenni az egyes fánkokat.
Józsika mindig csak a kupacok tetején lévő fánkok közül választhat (nem tud tetszőleges fánkot kivenni a kupacokból) és egyszerre csak egy fánkot ehet.
Maximum hány darab fánkot tud megenni Józsika az apja érkezéséig?
Standard bemenet formátuma:
n m X
A₁,A₂...Aₙ
B₁,B₂...Bₘ
"n" és "m" 1 és 100 000 közötti integer
"X", "Aᵢ" és "Bᵢ" 1 és 10 000 000 közötti integer
A megoldást a standard kimenetre írjuk.
Például:
2 5 50
5 20
30 10 10 40 20
Megoldás: 3
Magyarázat: Két optimális megoldás van, Józsika megeszik 3 fánkot a B kupacból (30 + 10 + 10 <= 50) vagy 1-et az A kupacból és 2-t a B kupacból (5 + 30 + 10 <= 50).
Ha például megenné mindkét fánkot az A kupacból, akkor a B-ből már nem tudna megenni egyet sem (mert 5 + 20 + 30 > 50).
A input beolvasása megy ebből de nem tudom hogyan tovább :D
Először azzal próbálkoztam hogy mindig a legkisebb értéket választom de ez nem jó megoldás mert előfordulhat, hogy a nagyobb értéket kell választani a kisebb végső összeg érdekében.
A standard bemenet formátumot rosszul írtam (nincsenek vesszők benne) de a példából látszik a jó formátum.
n m X
A₁ A₂ ... Aₙ
B₁ B₂ ... Bₘ
De végülis mindegy is mert nem a beolvasással van problémám.
válasza: válasza:** "ld. például "Visszalépéses keresés""
Illetve annyi könnyebbség van, hogy nem kell minden csomópontot végigjárni, mert már az odavezető úton is eldől, érdemes-e tovább vizsgálni azt az ágat, pl. már félúton rosszabb, mint az eddigi legjobb.
válasza:
válasza:Nem hiszem, hogy kvantumszámítógépe van a kérdezőnek, amivel százezres nagyságrendnél backtrackingelhet (de ha mégis, akkor is felesleges exponenciális megoldást alkalmazni, ha van lineáris is).
Számolsz 2 prefix sumot a kupacokból, elindulsz 2 pointerrel az egyik elejéről, a másik végéről és ahol a párok összege nem nagyobb, mint x, az a pont potenciális megoldás, ezek közül kell az, ahol a fánkok száma a legnagyobb.
válasza:#5, A kérdező példájával levezetnéd ezt röviden, kérlek?
Tehát pl.
5 20 / 30 10 10 40 20 (bemenet)
5 25 / 30 40 50 90 110 (prefix sums)
...
válasza:Célszerű 0-val kezdeni a sumot. Állsz A elején, B végén, ha az összeg nagyobb X-nél, akkor rossz megoldás -> feljebb lépsz B-ben, ha nem nagyobb, akkor jó megoldás -> lejjebb lépsz A-ban.
Elég triviális, nem tudom mit kéne még levezetni rajta.
válasza:A lekezelő stílusod nem sokat segített, de amúgy kezdem érteni, mire akarsz kilyukadni. A gond az, hogy mennyivel jobb, ha egy százezres nagyságrendű lista végéről indulsz visszafelé? Egyébként kb. ugyanazt írtad, amit én, csak én nem megyek végig a teljes listán. Egyébként annyira nem bonyolult az a fa, nem is kell végig bejárni, és szerintem kevesebb lépésben ad eredményt.
De részemről ennyi, majd a kérdező eldönti, hogy csinálja.
válasza: válasza:Kapcsolódó kérdések:
Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!