Megoldás
Átfogalmazzuk a vírusok intervallumba tartozására kapott három egyenlőtlenséget: egy K kezdési idejű P pusztulási idejű (a továbbiakban K-P) vírus akkor van egy T kezdetű H hosszú intervallumban, ha:
- A vírus létezett a T, T+1, ..., T+H-1 időpontok valamelyikében.
- A vírusról tudjuk, hogy a K, K+1, ..., P-1 időpontokban létezett.
1. megoldás
Felveszünk egy 7000 elemű tömböt, minden eleme egy időpontot reprezentál. Legyen virusok[t] értéke a T kezdetű, H hosszú időintervallumban megfigyelhető vírusok száma. Ezen tömb értéke a bemeneti fájl betöltése közben meghatározható: kezdetben minden eleme nulla, majd minden vírusra növeljük a megfelelő elemeket. Végül a tömbökből egy maximum-kereséssel kiolvashatók a keresett eredmények.
Eljárás VirusBetesz(k, p)
k := k - h + 1;
Ha k < 1 Akkor k := 1;
Ciklus i := k-tól p-1-ig
virusok[i]:= virusok[i]+1;
Ciklus Vége
Eljárás Vége
Ez az algoritmus $O\left(N \left(h_{\'{a}}+H\right) \right)$ időben fog lefutni, ahol $h_{\'{a}}$ a vírusok életének átlagos hossza.
2. megoldás
Programunkon a VírusBetesz() eljárá konstans idejűvé tételén lehet gyorsítani. A virus tömb helyett használjuk inkább a virus2[] tömböt, amit a következő módon hozunk létre:
Eljárás VírusBetesz(k, p)
k := k - h + 1;
Ha k < 1 Akkor k := 1;
virus2[k]:= virus2[k] - 1;
virus2[p]:= virus2[p] + 1;
Eljárás Vége
Végiggondolható, hogy innen: virus2[1] = virus[1], majd i > 1-re: virus2[i] = virus[i] - virus[i-1]. Így a maximumkiválasztási ciklusban az eredeti tömb értékét egy számlálóv-változóval nyerhetjük vissza.
Így ez az algoritmus már lefut $O\left(N\right)$ időben...
Megjegyzés
A verseny elvárásaitól függ, hogy egy ilyen gyorsítását meg kell-e írni. OKTV/NTTV versenyeken valószínűleg nem fog kelleni...
TODO:
idő-összehasonlítás a két program között, rajzok, részletezés(?)
Megoldások
