Ezt hogy csináljam meg?
Egy étteremben minden nap A és B menü közül válaszhatunk. Megkapjuk az étterem menüjét N napra előre (maximum egy évre előre). Mennyi a legkisebb összeg amit fizetnünk kell ha minden nap enni akarunk de ugyanazt a menüt maximum 2 egymást követő napon választhatjuk?
A menüt egy Nx2-es 2D tömbként kapom meg ahol a sorok a napok a két oszlop pedig az A és B menü árai. Pl:
4 6
3 7
2 8
6 1
Itt a megoldás 6 + 3 + 2 + 1 = 12.
(4 + 3 + 2 + 1 nem lehet mert úgy 3 egymást követő napon választanánk az A menüt)
Ezt csináltam:
De így nem jó mert egyrészt nem mindig a legkisebbet kéne választani csak nem tudom hogy döntsem el. Másrészt nem tudom hogy figyeljem hogy választottam-e már 2x egymás után ugyanazt.
válasza: válasza: válasza: válasza:Amúgy van még egy megoldás, ami szerintem jó lehet és gyorsan fog futni, ráadásul vissza se kell lépkedni.
Rendezd a tömböt az első érték szerint növekvő sorrendbe:
pl:
4 6
3 7
2 8
6 1
Esetén a rendezett tömb:
2 8
3 7
4 6
6 1
Ezután mindig a minimumot keresed, de minden 3.-nál a maximumot veszed. Tehát
2,3, (Most jön a 3.: 6), és utána 1
Másik példa:
2 3
4 5
6 7
3 6
4 7
Rendezve:
2 3
3 6
4 5
4 7
6 7
2,3 (Most a maximumot: 5) 4,6 = 20
válasza:16-os:
1 5
5 1
1 5
5 1
1 5
5 1
Rendezve első érték szerint:
1 5
1 5
1 5
5 1
5 1
5 1
Így a te logikád szerint ha jól értem 1+1+5+1+1+5=14 lenne a megoldás, a jó megoldás pedig 1+1+1+1+1+1=6.
17-es hogy építed fel úgy a gráfot?
Vegyük a kérdésben szereplő példát:
4 6
3 7
2 8
6 1
4-ből 3-ba és 7-be menne él így 7-ből pedig 8-ba mert 4-7-8 ugye jó út.
6-ból szintén mennie kéne ugye 3-ba és 7-be viszont mivel 7-ből 8-ba már vezet él így elérhetővé válna a 6-7-8 ami rossz út.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, 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!