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

• #8958 axioma veterán peterszky #8956

  Új Válasz 2015-09-16 11:11:44 #8958

  Ú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

  Privát üzenet küldése

  

  axioma

  veterán

  válasz peterszky #8956 üzenetére

  Ismetlesnel arra gondoltam, hogy ugyanaz az index 2x lehet-e (egy szam - ha csak 1x van is - felhasznalhato-e ketszer), de gondolom akkor nem.
  Ja, hogy az 1%-ot ugy erted, hogy akkor nem jon ki, amikor a (melysegi) kereses nem talalja meg az elejen... azaz nem is nem jon ki, hanem nem varjatok ki.
  Ha ezek penzosszegek, akkor gondolom lehet felso korlat a szummara, mondjuk 10M. Teged pedig legfeljebb a 10M alatti osszes szam _egyfele_ osszeallitasa erdekel. DE: az egyes ertekekhez me'g erre sincs szukseged. Eleg az utolso elemet tudni, ami kellett ahhoz, hogy o osszealljon. (Az egyikben.)
  Szoval reszemrol a kovetkezo algot probalnam be:
  map int->int
  indulaskor 0->0
  csokkeno sorrendben a szamok, mindegyiknel a map minden elemehez hozzaadod, es ha kisebb a celszamnal es nincs me'g benne, akkor beteszed az uj szamot rendelve hozza.
  amikor megkapod a celszamot pont, akkor abort, es visszakeresed: a map-ben milyen szamot irtal melle, kivonod a celszamobol azt, es keresed a map-ben a maradekot. Ismetled amig a 0->0-hoz nem jutsz. Voila, megvan a keresett halmaz.
  Ez igy ordo max^2*darabszam ordo max^2*ln(max)*darabszam (a map koltsegigenye miatt) komplexitas idoben, es ordo max tarhelyben. Azt neked kell tudnod, hogy ez belefer-e.
  Ilyesfajta megoldasra gondoltal?

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