AlgoritmusBináris keresést alkalmazunk. A leghosszabb levágható kábel nem lehet hosszabb a legnagyobb raktáron levő kábel hosszánál. Legyen ez a maximum M. A [0; M] intervallumban keressük a legnagyobb "jó" méretet. Egy méret akkor jó, ha lehetséges K ilyen méretű kábel vágása. Ha egy x méret jó, akkor nyilván minden x-nél kisebb méret is jó, ha pedig rossz, akkor minden nála nagyobb méret is rossz, ezért alkalmazható a bináris keresés. Kódok
|