Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku nášho testovača a budeš riešiť sadu Úvod do programovania. Každou z úloh Číslo, Zámena, Obdĺžnik 1 si vieš nahradiť 5 bodov z tejto úlohy. Pomôcť si vieš Python tutoriálom, ktorý sme pre teba nachystali. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na testovači.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Maťovi na [email protected]
Adam si na desiatu spravil masívnu, $n$ centimentrov dlhú bagetu. Potom ale zistil, že sa mu celá nezmestí do ruksaku. Rozhodol sa, že z nej aspoň vyreže úsek dlhý $k$ cm a ten už zbalí bez problémov. Rozloženie surovín v bagete ale nie je rovnomerné a na niektorých miestach chutí lepšie ako na iných. Adam sa preto rozhodol, že si vyberie taký úsek, ktorý chutí najlepšie.
Na vstupe dostanete čísla $n$, $k$ a popis bagety, teda pre každý centimetrový dielik bagety dostanete na vstupe jedno celé číslo, jeho chuť. Chuť vybraného úseku bagety je súčet chutí dielikov, z ktorých sa skladá. Vašou úlohou je vypísať chuť najchutnejšieho súvislého úseku dĺžky presne $k$.
Pozor, vami vybraný úsek nemôže byť kratší ako $k$ centimetrov, bez ohľadu na to ako nechutný by bol. Adam by tak totiž ostal hladný.
Na prvom riadku vstupu sú dve čísla $n$ a $k$ ($1\leq k\leq n \leq 10^6$) – pôvodná dĺžka bagety a dĺžka úseku, ktorý z nej máte vyrezať.
Na druhom riadku je $n$ medzerou oddelených čísel $c_1$ až $c_n$, chuť jednotlivých dielikov. Platí, že $-10^9\leq c_i\leq10^9$.
Na jediný riadok výstupu vypíšte číslo $x$ – chuť najchutnejšieho súvislého úseku dĺžky $k$ cm.
Vaše riešenie bude testované na 5 sadách vstupov, za každý môžete získať 3 body. Pre prvé dve sady platí, že $n \leq 1\,000$.
7 3
-2 5 7 3 9 -10 14
19
Najchutnejší úsek, ktorý môže Adam z bagety vyrezať obsahuje 3, 4 a 5 centimeter s celkovou chuťou $7+3+9 = 19$. Zvyšné úseky, napríklad 2 až 4 centimeter s chuťou 15 alebo 5 až 7 centimeter s chuťou 13, nie sú natoľko chutné.
Priamočiary spôsob ako nájsť najchutnejší úsek je pre každý možný úsek zrátať jeho chuť a z nich potom vybrať ten najlepší. Označme si teda $u_i$ chuť úseku, ktorý začína na $i$-tej pozícii. Tieto hodnoty potom vieme vypočítať ako:
$$ u_1=c_1+c_2+\dots+c_k$$ $$u_2=c_2+c_3+\dots+c_{k+1}$$ $$\dots$$ $$u_{n-k+1}=c_{n-k+1}+c_{n-k+2}+\dots+c_n $$
Následne nám stačí vybrať to najväčšie.
Pre každý úsek musíme sčítať $k$ čísel a úsekov je dokopy $n-k+1$. To nám dáva časovú zložitosť $O(k(n-k))$, čo je v najhoršom prípade $O(n^2)$.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
long long maxSucet = -9999999999999999LL;
for(int i = 0; i < n-k+1;i++)
{
long long sucet = 0;
for(int j = 0; j < k; j++) sucet+=v[i+j];
maxSucet = max(sucet,maxSucet);
}
cout << maxSucet << "\n";
}
Aby sme dosiahli rýchlejšie riešenie, môžeme sa pokúsiť zlepšiť spôsob akým počítame chuť jednotlivých úsekov. Na to si stačí uvedomiť, že dva po sebe idúce úseky spolu zdieľajú väčšinu dielikov:
$$ u_1=c_1+(c_2+\dots+c_k)$$ $$u_2=(c_2+\dots+c_k)+c_{k+1} $$
Z toho vidno, že:
$u_2=u_1-c_1+c_{k+1}$
Takto môžeme pokračovať:
$$ u_3=u_2-c_2+c_{k+2}$$ $$\dots$$ $$u_{n-k+1}=u_{n-k}-c_{n-k}+c_n $$
Hodnotu $u_1$ musíme stále vypočítať normálne (sčítaním $k$ čísel) v čase $O(k)$. Zvyšných $n-k$ úsekov už ale vieme každý spočítať v konštantnom čase, výsledkom čoho bude časová zložitoť $O(n)$.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
queue<long long> Q;
long long sucet = 0;
long long maxSucet = -9999999999999999LL;
for(int i = 0; i < n; i++)
{
long long x;
cin >> x;
sucet+=x;
Q.push(x);
if(Q.size() > k)
{
sucet -= Q.front();
Q.pop();
}
if(Q.size() == k) maxSucet = max(sucet, maxSucet);
}
cout << maxSucet << "\n";
}
n, k = list(map(int, input().split()))
cisla = list(map(int, input().split()))
maxSucet = -9999999999999999
sucet = 0
for i in range(n):
sucet += cisla[i]
if i >= k:
sucet -= cisla[i-k]
if i >= k-1:
maxSucet = max(sucet, maxSucet)
print(maxSucet)