Co już umiesz i czego się nauczysz
Ta lekcja zakłada, że przerobiłeś wszystkie poprzednie: Typy zmiennych, Input / Output, If / Else, While loop, For loop, Modulo, Tablice, String, Pair, Vector i Sortowanie. Niczego nowego o samym języku nie trzeba tu znać — wystarczą pętle, if, tablice i vector.
Z funkcjami max i min już się mijałeś: pojawiły się na chwilę w lekcji o instrukcji if, przy przedziałach w lekcji o parach, a w lekcji o vectorze poznałeś strzałkę max_element. Za każdym razem były jednak tylko dodatkiem. Teraz dostają własną lekcję, bo szukanie największej i najmniejszej wartości to jedna z najczęstszych rzeczy w programowaniu — i pełno w niej pułapek: od czego zacząć rekord? Co, gdy wszystkie liczby są ujemne? Co, gdy rekord się powtarza? Dlaczego max(3, 2.5) się nie kompiluje? Jak znaleźć drugą największą liczbę?
Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw zapisz sobie na kartce zmienne (na przykład maks i mini) i śledź program linijka po linijce, a dopiero potem sprawdzaj odpowiedź. Animacje możesz klikać krok po kroku — spróbuj za każdym razem przewidzieć, co stanie się po kliknięciu. Po każdej części rób ćwiczenia w sprawdzarce. Lekcja jest długa: rób przerwy i nie przechodź dalej, dopóki ćwiczenia z poprzedniej części nie przestaną sprawiać Ci kłopotu.
Kilka liczb
max(a, b) i min(a, b) od podstaw, pułapka różnych typów, trzy liczby, lista w klamrach i liczba środkowa.
Rekord w danych
Rekord w pętli i wartość startowa, pozycja rekordu i remisy, a potem gotowce max_element i min_element.
Granice i dwie najlepsze
„Nie mniej niż zero, nie więcej niż limit”, wspólna część przedziałów, dwie największe liczby i najlepsza para.
Max i min w akcji
Rekordy liczone na bieżąco, najlepszy zysk, najdłuższa seria, najlepsze okno, największa suma fragmentu i tabele.
cout << x << " " jest w porządku. W tej lekcji szczególnie uważaj na ograniczenia w treści zadania: to one mówią, czy liczby mogą być ujemne i czy wynik zmieści się w int, czy potrzebny będzie long long.
Mapa lekcji
max i min — większa i mniejsza z dwóch
Zaczynamy od najprostszej sytuacji: masz dwie liczby i chcesz wiedzieć, która jest większa. Umiesz to już zrobić instrukcją if, ale C++ ma na to dwie gotowe funkcje, które będziesz pisać tysiące razy: max i min. W tej części zobaczysz, jak działają, co dokładnie „oddają”, jak zachowują się dla liczb ujemnych, liter i napisów, oraz poznasz jedyną pułapkę, na którą trzeba uważać — typy.
Pierwszy program
max(a, b) to większa z liczb a i b, a min(a, b) to mniejsza. Nazwy pochodzą od łacińskich słów maximum (największy) i minimum (najmniejszy). Obie funkcje mieszkają w bibliotece <algorithm>, ale <bits/stdc++.h> ma ją w środku, więc niczego nie dopisujesz.
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
cout << max(a, b) << "\n"; // większa
cout << min(a, b) << "\n"; // mniejsza
return 0;
}
Ten sam program uruchomiliśmy trzy razy, z różnymi danymi.
Za pierwszym razem wszystko jest oczywiste: 7 jest większe od 3.
Za drugim razem liczby są ujemne. Która jest większa: −4 czy −9? Większa jest ta, która leży bardziej na prawo na osi liczbowej, czyli bliżej zera: −4. Program to wie — nie musisz się o to martwić.
Za trzecim razem liczby są równe. Wtedy i większa, i mniejsza to po prostu 5. Nie ma tu żadnego błędu ani wyjątku.
| zapis | wynik | dlaczego |
|---|---|---|
max(3, 8) | 8 | 8 jest większe od 3 |
min(3, 8) | 3 | 3 jest mniejsze od 8 |
max(-3, -8) | −3 | −3 leży bliżej zera, bardziej na prawo na osi |
min(-3, -8) | −8 | −8 leży dalej na lewo |
max(0, -5) | 0 | każda liczba ujemna jest mniejsza od zera |
min(6, 6) | 6 | gdy liczby są równe, wynik jest taki sam |
max oddaje wartość — możesz jej użyć, jak chcesz
Pomyśl o max(a, b) jak o działaniu, tak jak o a + b. Komputer je wylicza i w tym miejscu programu pojawia się wynik. Taki wynik możesz wypisać, zapisać do zmiennej, pomnożyć, dodać do czegoś albo porównać — wszystko, co robisz ze zwykłą liczbą.
int a = 12, b = 30;
int w = max(a, b); // w = 30
cout << w << "\n";
cout << max(a, b) * 2 << "\n"; // 30 * 2
cout << max(a, b) - min(a, b) << "\n"; // 30 - 12
cout << max(a, 20) << "\n"; // a z liczbą
cout << a << " " << b << "\n"; // a i b bez zmian
Zwróć uwagę na trzy rzeczy.
Argumentami nie muszą być zmienne — max(a, 20) porównuje zmienną z liczbą.
max(a, b) - min(a, b) to odległość między liczbami: od większej odejmujemy mniejszą, więc wynik nigdy nie jest ujemny. To dokładnie to samo co abs(a - b).
Ostatni wiersz: max i min niczego nie zmieniają. Tylko patrzą na a i b i oddają wynik. Zmienne mają te same wartości co na początku.
max(a, b); w osobnej linijce, a potem cout << a; w nadziei, że w a jest teraz większa liczba. Nie jest! Funkcja policzyła wynik, ale nikt go nie zapisał ani nie wypisał, więc przepadł. Jeśli chcesz, żeby a stało się większą z dwóch liczb, napisz a = max(a, b);. Kompilator z włączonymi ostrzeżeniami (-Wall) nawet o tym przypomni: warning: ignoring return value of max — „ignorujesz wynik funkcji max”.
int a = 4, b = 9;
max(a, b); // wynik nikomu się nie przydał
cout << a << "\n";
a = max(a, b); // teraz zapisujemy go do a
cout << a << "\n";
Zapis a = max(a, b); czytaj tak: „nowe a to większa z liczb: stare a i b”. Jeśli b było większe, a dostaje wartość b. Jeśli nie — a zostaje takie, jakie było.
Ten zapis będzie bohaterem części 3: w pętli zamieni się w maks = max(maks, x); — rekord, który poprawia się z każdą wczytaną liczbą.
To samo bez max — dla porównania
Żeby nie było w tym magii: max robi dokładnie to, co umiesz już napisać instrukcją if. Poniżej trzy sposoby na tę samą rzecz. Wszystkie dają ten sam wynik — ale wersja z max mieści się w jednej krótkiej linijce i trudniej się w niej pomylić.
int a = 8, b = 13;
int w1; // sposób 1: if / else
if (a > b) w1 = a;
else w1 = b;
int w2 = (a > b ? a : b); // sposób 2: ?: z lekcji o if
int w3 = max(a, b); // sposób 3: max
cout << w1 << " " << w2 << " " << w3 << "\n";
Kiedy więc wybrać if, a kiedy max? Gdy chcesz tylko poznać większą liczbę — max. Gdy przy okazji musisz zrobić coś więcej (zapamiętać, kto miał więcej punktów, albo wypisać komunikat) — if. Do tej drugiej sytuacji wrócimy w części 4.
Najważniejsza pułapka: oba argumenty tego samego typu
max i min mają jeden kaprys: oba argumenty muszą być dokładnie tego samego typu. Dwa int-y — dobrze. Dwa double — dobrze. Ale int i double naraz — błąd kompilacji, i to z długim, strasznym komunikatem, w którym zobaczysz coś w rodzaju no matching function for call to max(int, double) oraz deduced conflicting types. Kompilator nie wie, jakiego typu ma być wynik, więc się poddaje.
cout << max(3, 2.5) << "\n"; // int i double — błąd
cout << max(3.0, 2.5) << "\n"; // dwa double
int a = 3;
double b = 2.5;
cout << max((double)a, b) << "\n"; // a zamienione na double
cout << max(1.5, 2.25) << "\n";
Liczba 3 to dla C++ int, a 3.0 to double. Gdy porównujesz zmienną typu int ze zmienną typu double, zamień jedną z nich przed porównaniem: (double)a to wartość a jako double — tak samo jak w lekcji o typach zmiennych.
Najczęściej ta pułapka łapie przy long long. Liczba 7 napisana w programie to int, więc max(x, 7) dla long long x się nie skompiluje. Dopisz na końcu liczby literki LL — wtedy 7LL jest typu long long — albo zamień ją: (long long)7.
long long x = 5000000000LL;
cout << max(x, 7) << "\n"; // long long i int — błąd
long long x = 5000000000LL; // 5 miliardów — nie mieści się w int
cout << max(x, 7LL) << "\n";
cout << min(x, (long long)7) << "\n";
max(int, int) ✓ · max(double, double) ✓ · max(long long, long long) ✓ · max(int, double) ✗ · max(long long, int) ✗. Gdy kompilator krzyczy „no matching function for call to max”, prawie zawsze chodzi o to, że argumenty mają różne typy. Poprawka: 3.0 zamiast 3, 7LL zamiast 7 albo zamiana typu w nawiasie, np. (double)a.
Nie tylko liczby: znaki i napisy
max i min działają dla wszystkiego, co da się porównać znakiem <. Znaki porównują się po kodach (pamiętasz z lekcji o napisach: wielkie litery 65–90, małe 97–122), a napisy — w porządku słownikowym, litera po literze. Pary z lekcji o parach też: najpierw po first, a przy remisie po second.
cout << max('k', 'c') << "\n";
cout << min('Z', 'a') << "\n"; // 'Z' ma kod 90, 'a' — 97
string s = "kot", t = "kotek";
cout << max(s, t) << "\n";
cout << min(s, t) << "\n";
pair<int, int> p = {2, 9}, q = {2, 5};
cout << max(p, q).second << "\n"; // remis na first, wygrywa second
max('k', 'c') to litera, która jest dalej w alfabecie.
min('Z', 'a') to wielkie Z, bo wszystkie wielkie litery mają mniejsze kody od małych — tak samo jak przy sortowaniu.
Napis „kot” jest początkiem napisu „kotek”, więc w słowniku stoi wcześniej — jest „mniejszy”.
Pary (2, 9) i (2, 5) remisują na first, więc rozstrzyga second: większa jest (2, 9).
Dwa przykłady z życia
W prawdziwych zadaniach max i min rzadko pojawiają się „gołe”. Zwykle w treści jest słowo: lepszy, tańszy, dłuższy, wcześniejszy. Twoim zadaniem jest przetłumaczyć je na max albo min.
// Zawodnik oddaje dwa skoki, liczy się lepszy.
double s1, s2;
cin >> s1 >> s2;
cout << "Wynik: " << max(s1, s2) << "\n";
// Ta sama rzecz w dwóch sklepach — kupujemy taniej.
int sklepA, sklepB;
cin >> sklepA >> sklepB;
cout << "Zaplacisz: " << min(sklepA, sklepB) << "\n";
cout << "Oszczedzisz: " << max(sklepA, sklepB) - min(sklepA, sklepB) << "\n";
max · mniejszy, tańszy, krótszy, niższy, wcześniejszy, „co najwyżej”, „nie więcej niż” → najczęściej min. Uwaga na czas: „najlepszy czas biegu” to najkrótszy, czyli min!
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << max(4, 9) << min(4, 9);
Pokaż odpowiedź
cout << max(-2, -7);
Pokaż odpowiedź
int a = 5;
max(a, 10);
cout << a;
Pokaż odpowiedź
max nie został nigdzie zapisany, więc przepadł. a się nie zmieniło.int a = 5;
a = max(a, 10);
a = min(a, 7);
cout << a;
Pokaż odpowiedź
cout << max('a', 'B');
Pokaż odpowiedź
cout << min(7, 7) + max(3, 3);
Pokaż odpowiedź
int a = 3, b = 8;
cout << max(a, b) - min(a, b) << " ";
cout << min(a, b) - max(a, b);
Pokaż odpowiedź
string x = "ala", y = "Ola";
cout << max(x, y);
Pokaż odpowiedź
cout << max(2.5, 2.25) * 2;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Trzy, cztery, pięć liczb — max w max i lista w klamrach
max(a, b) porównuje dokładnie dwie liczby. A co, gdy liczb jest trzy albo pięć? Są dwa sposoby: wkładać jedno max w drugie albo podać wszystkie liczby naraz w klamrach. Poznasz oba, a potem użyjesz ich do trzech klasycznych zadań: noty sędziów, liczba środkowa i trójkąt.
max w max — czytamy od środka
Największą z trzech liczb dostaniesz tak: max(a, max(b, c)). Komputer liczy to od środka, tak jak nawiasy w matematyce: najpierw max(b, c) — większa z b i c — a potem porównuje ten wynik z a. To jak turniej: najpierw grają b i c, a zwycięzca gra w finale z a.
int a = 4, b = 9, c = 6;
cout << max(a, max(b, c)) << "\n";
cout << min(a, min(b, c)) << "\n";
cout << max(max(a, b), c) << "\n"; // inna kolejność, ten sam wynik
| krok | co liczymy | wynik |
|---|---|---|
| 1 | max(b, c) = max(9, 6) | 9 |
| 2 | max(a, 9) = max(4, 9) | 9 |
Kolejność „meczów” nie ma znaczenia: największa liczba wygra każdy mecz, w którym zagra, więc zawsze dojdzie do końca.
Dla czterech liczb wkładamy jeszcze głębiej: max(max(a, b), max(c, d)) — dwa półfinały i finał. Działa, ale przy pięciu liczbach nawiasów robi się tyle, że łatwo się w nich zgubić. Dlatego jest drugi sposób.
Lista w klamrach: max({…})
Wszystkie liczby możesz podać naraz, w klamrach wewnątrz nawiasów: max({a, b, c, d, e}). Klamry tworzą listę — taką samą, jakiej używałeś do wypełniania vectora: vector<int> v = {4, 9, 6};. Liczb w liście może być dowolnie wiele.
int a = 4, b = 9, c = 6, d = -2, e = 9;
cout << max({a, b, c, d, e}) << "\n";
cout << min({a, b, c, d, e}) << "\n";
cout << max({3, 1, 4, 1, 5, 9, 2, 6}) << "\n";
long long x = 7000000000LL;
cout << max({x, 5LL, 0LL}) << "\n"; // wszystkie long long
Zasada jednego typu z części 1 obowiązuje także tutaj: wszystkie elementy listy muszą mieć ten sam typ. Dlatego przy long long x piszemy 5LL i 0LL.
Uważaj na nawiasy: klamry są w środku okrągłych. max(3, 8, 5) bez klamer to błąd — trzecie miejsce w nawiasie jest zarezerwowane na coś zupełnie innego (regułę porównania, jak w sort), a liczba 5 regułą nie jest.
cout << max(3, 8, 5) << "\n"; // brak klamer — błąd
max(a, b). Trzy i więcej: max({a, b, c}) — klamry w środku nawiasów. Wszystkie elementy tego samego typu.
Noty sędziów: odrzuć najwyższą i najniższą
W skokach narciarskich pięciu sędziów ocenia styl skoczka. Żeby jeden zbyt surowy albo zbyt łaskawy sędzia nie zepsuł wyniku, odrzuca się najwyższą i najniższą notę, a pozostałe trzy się sumuje. W programie to jedna linijka: suma wszystkich minus największa minus najmniejsza.
#include <bits/stdc++.h>
using namespace std;
int main() {
double n1, n2, n3, n4, n5;
cin >> n1 >> n2 >> n3 >> n4 >> n5;
double suma = n1 + n2 + n3 + n4 + n5;
double najw = max({n1, n2, n3, n4, n5});
double najm = min({n1, n2, n3, n4, n5});
cout << suma - najw - najm << "\n";
return 0;
}
Suma wszystkich not: 18.5 + 19 + 17.5 + 18 + 20 = 93.
Najwyższa nota to 20, najniższa — 17.5. Odrzucamy je: 93 − 20 − 17.5 = 55.5, czyli suma not 18.5, 19 i 18.
A gdyby dwóch sędziów dało po 20? Odrzucamy tylko jedną z nich — i program robi dokładnie to, bo od sumy odejmuje liczbę 20 tylko raz.
Liczba środkowa i trzy liczby po kolei
Z trzech liczb jedna jest największa, jedna najmniejsza, a trzecia — środkowa. Jak ją znaleźć bez sortowania? Tą samą sztuczką co przy sędziach: od sumy wszystkich trzech odejmij największą i najmniejszą. Zostaje dokładnie ta trzecia. Mając wszystkie trzy, możesz wypisać liczby po kolei.
int a, b, c;
cin >> a >> b >> c;
int mn = min({a, b, c});
int mx = max({a, b, c});
int sr = a + b + c - mn - mx;
cout << mn << " " << sr << " " << mx << "\n";
Pierwsze dane: suma to 14, największa 7, najmniejsza 2, więc środkowa to 14 − 7 − 2 = 5.
Drugie dane: dwie czwórki. Najmniejsza to 4, największa 9, a środkowa 17 − 9 − 4 = 4 — druga czwórka. Sztuczka działa także przy powtórzeniach.
int (około 2,1 miliarda) i wynik wyjdzie bez sensu. W takim zadaniu wczytuj liczby do long long — i pamiętaj, że wtedy wszystkie argumenty max i min też muszą być long long.
Czy z trzech patyków zbudujesz trójkąt?
Masz trzy patyki o długościach a, b i c. Trójkąt da się zbudować wtedy, gdy najdłuższy patyk jest krótszy od dwóch pozostałych razem. Jeśli jest równy ich sumie albo dłuższy, dwa krótsze patyki „nie dosięgną” do siebie. Sprawdzać wszystkie trzy warunki (a < b + c, b < a + c, c < a + b) nie trzeba — wystarczy jeden, dla najdłuższego.
long long a, b, c;
cin >> a >> b >> c;
long long najdl = max({a, b, c});
long long reszta = a + b + c - najdl; // suma dwóch krótszych
if (najdl < reszta) cout << "TAK\n";
else cout << "NIE\n";
3, 4, 5: najdłuższy ma 5, pozostałe razem 7. 5 < 7 — trójkąt jest.
1, 2, 3: najdłuższy ma 3, pozostałe razem też 3. Patyki ułożyłyby się w płaski odcinek, a nie w trójkąt — NIE.
10, 3, 4: patyki 3 i 4 razem mają 7, a to mniej niż 10 — NIE.
Używamy long long, bo patyki mogą być długie, a ich suma większa od zakresu int.
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
cout << max(3, max(8, 5));
Pokaż odpowiedź
cout << min(min(4, -1), 2);
Pokaż odpowiedź
cout << max({3, 9, 4, 9});
Pokaż odpowiedź
int a = 6, b = 1, c = 4;
cout << a + b + c - max({a, b, c}) - min({a, b, c});
Pokaż odpowiedź
cout << max(min(5, 2), min(3, 7));
Pokaż odpowiedź
cout << min({7, 3, 5}) * max({1, 2});
Pokaż odpowiedź
long long x = 4;
cout << max({x, 10LL, 2LL});
Pokaż odpowiedź
cout << max(max(1, 2), max(3, 4)) - min(min(1, 2), min(3, 4));
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Rekord: maks = max(maks, x)
Lista w klamrach działa, gdy liczb jest kilka i znasz je, pisząc program. Ale w zadaniach liczb jest zwykle n — i n poznajesz dopiero po wczytaniu danych. Może ich być pięć, a może sto tysięcy. Wtedy potrzebny jest rekord: jedna zmienna, która pamięta najlepszą wartość widzianą do tej pory i poprawia się przy każdej kolejnej liczbie. To najważniejszy schemat tej lekcji — rekord pojawi się prawie w każdym zadaniu.
Sędzia na zawodach w skoku w dal
Sędzia nie musi zapisywać wszystkich skoków, żeby po zawodach wiedzieć, który był najdłuższy. Wystarczy, że trzyma w głowie dotychczasowy rekord. Po każdym skoku porównuje: jeśli nowy skok jest dłuższy, rekord się zmienia; jeśli nie — zostaje. Po ostatnim skoku rekord jest wynikiem całych zawodów. W programie „porównaj i weź lepszy” to dokładnie maks = max(maks, x);.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int maks;
cin >> maks; // pierwsza liczba = rekord na start
for (int i = 1; i < n; i++) {
int x;
cin >> x;
maks = max(maks, x); // lepszy z: stary rekord, x
}
cout << maks << "\n";
return 0;
}
| i | x | maks przed | maks po |
|---|---|---|---|
| start | — | — | 38 |
| 1 | 27 | 38 | 38 |
| 2 | 43 | 38 | 43 |
| 3 | 3 | 43 | 43 |
| 4 | 9 | 43 | 43 |
| 5 | 82 | 43 | 82 |
| 6 | 10 | 82 | 82 |
| 7 | 56 | 82 | 82 |
Pierwszą liczbę wczytujemy przed pętlą i od razu robimy z niej rekord. Dlatego pętla zaczyna się od i = 1 — przechodzi już tylko po pozostałych n − 1 liczbach. Zauważ też, że nie potrzebujemy ani tablicy, ani vectora: każdą liczbę oglądamy raz, porównujemy z rekordem i zapominamy. Program działa tak samo dla 8 liczb i dla miliona.
Od czego zacząć rekord? Pułapka zera
Kusi, żeby zacząć od int maks = 0; i wczytywać wszystkie liczby w pętli. Dla liczb dodatnich to nawet zadziała. Ale zobacz, co się stanie, gdy wszystkie liczby są ujemne:
int n;
cin >> n;
int maks = 0; // ZŁY start!
for (int i = 0; i < n; i++) {
int x;
cin >> x;
maks = max(maks, x);
}
cout << maks << "\n";
Żadna z liczb −7, −2, −15, −3 nie jest większa od zera, więc rekord ani razu się nie zmienił i program wypisał 0 — liczbę, której w ogóle nie ma w danych. Poprawna odpowiedź to −2.
To jeden z najczęstszych błędów na zawodach, bo program przechodzi przykład z treści (zwykle z liczbami dodatnimi), a pada dopiero na ukrytym teście z ujemnymi. Z min jest tak samo: start od 0 przy samych dodatnich liczbach daje 0.
Są dwa bezpieczne sposoby. Pierwszy: zacznij od pierwszej liczby z danych — ona na pewno w nich jest. Drugi: zacznij od liczby, która na pewno jest gorsza od każdej możliwej. Dla maksimum to bardzo mała liczba, a dla minimum — bardzo duża. C++ ma na to gotowe stałe z lekcji o typach: INT_MIN (najmniejszy możliwy int, około −2,1 miliarda) i INT_MAX (największy, około 2,1 miliarda). Dla long long są LLONG_MIN i LLONG_MAX.
int n;
cin >> n;
int maks = INT_MIN; // gorszy od każdej liczby
int mini = INT_MAX; // większy od każdej liczby
for (int i = 0; i < n; i++) {
int x;
cin >> x;
maks = max(maks, x);
mini = min(mini, x);
}
cout << maks << " " << mini << "\n";
INT_MIN dla maksimum, INT_MAX dla minimum. 3) Nigdy 0, jeśli zadanie nie gwarantuje, że liczby są dodatnie (dla maksimum) albo ujemne (dla minimum). Ograniczenia w treści zadania mówią, jakie liczby mogą się pojawić — zawsze je czytaj.
Największa i najmniejsza w jednej pętli
Nic nie stoi na przeszkodzie, żeby w jednej pętli prowadzić dwa rekordy naraz: maks i mini. Każda liczba jest porównywana z oboma. Różnica między największą a najmniejszą liczbą ma swoją nazwę — rozstęp — i mówi, jak bardzo dane są „rozrzucone”.
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) cin >> x;
int maks = v[0], mini = v[0];
for (auto x : v) {
maks = max(maks, x);
mini = min(mini, x);
}
cout << "najwieksza: " << maks << "\n";
cout << "najmniejsza: " << mini << "\n";
cout << "rozstep: " << maks - mini << "\n";
Gdy liczby są już w vectorze, start od pierwszej to po prostu v[0]. Pętla „dla każdego” porówna v[0] samo ze sobą — nic się wtedy nie zmieni, więc nie trzeba go pomijać.
Uwaga: v[0] istnieje tylko wtedy, gdy vector nie jest pusty. Jeśli zadanie dopuszcza n = 0, trzeba ten przypadek obsłużyć osobno.
Rekord czegoś, co trzeba policzyć
Rekord nie musi dotyczyć samych wczytanych liczb. Często w każdym obrocie pętli najpierw coś liczysz — długość słowa, sumę cyfr, odległość — a dopiero ten wynik porównujesz z rekordem. Przy długości napisu czeka mała pułapka: s.size() nie jest typu int (to typ bez znaku, który poznałeś w lekcji o vectorze), więc zasada jednego typu każe go zamienić: (int)s.size().
vector<string> slowa = {"ala", "programowanie", "kot", "olimpiada"};
int najdl = 0; // długość nie bywa ujemna
for (auto s : slowa) {
najdl = max(najdl, (int)s.size());
}
cout << najdl << "\n";
string s = "kot";
int najdl = 0;
najdl = max(najdl, s.size()); // int i size_t — błąd
Tu start od zera jest w porządku — długość słowa nigdy nie jest ujemna, więc każde słowo „pobije” zero. Zero jest złe tylko wtedy, gdy wartości mogą być mniejsze od niego.
Rekord tylko z niektórych liczb
Co, jeśli szukasz największej liczby parzystej? Nie możesz zacząć od pierwszej liczby, bo może być nieparzysta. Nie możesz też zacząć od zera, bo parzyste liczby mogą być ujemne. A może parzystych nie ma wcale i trzeba wypisać BRAK? Rozwiązanie: dodatkowa zmienna bool jest, która mówi, czy rekord już istnieje. Pierwsza pasująca liczba zostaje rekordem bez porównywania.
int n;
cin >> n;
bool jest = false; // czy widzieliśmy już parzystą?
int maks = 0; // ważne dopiero, gdy jest == true
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
if (!jest || x > maks) maks = x;
jest = true;
}
}
if (jest) cout << maks << "\n";
else cout << "BRAK\n";
Warunek !jest || x > maks czytaj: „jeszcze nie mamy rekordu albo x jest lepszy od rekordu”. Pierwsza parzysta liczba (−4) wchodzi dzięki lewej części warunku, a każda następna musi już pokonać rekord: −10 nie jest większe od −4, więc wynik to −4.
W drugich danych żadna liczba nie jest parzysta, więc jest zostało false i program wypisał BRAK.
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int maks = 5;
int t[4] = {3, 8, 2, 8};
for (int i = 0; i < 4; i++) maks = max(maks, t[i]);
cout << maks;
Pokaż odpowiedź
int maks = 0;
int t[3] = {-5, -2, -9};
for (int i = 0; i < 3; i++) maks = max(maks, t[i]);
cout << maks;
Pokaż odpowiedź
int mini = 100;
vector<int> v = {300, 150, 200};
for (auto x : v) mini = min(mini, x);
cout << mini;
Pokaż odpowiedź
vector<int> v = {2, 5, 3, 7, 7, 1};
int maks = v[0], zmian = 0;
for (int i = 1; i < 6; i++) {
if (v[i] > maks) zmian++;
maks = max(maks, v[i]);
}
cout << maks << " " << zmian;
Pokaż odpowiedź
vector<string> w = {"ala", "kotek", "pies"};
int d = 0;
for (auto s : w) d = max(d, (int)s.size());
cout << d;
Pokaż odpowiedź
vector<int> v = {4, -1, 7, 2};
int mx = v[0], mn = v[0];
for (auto x : v) { mx = max(mx, x); mn = min(mn, x); }
cout << mx - mn;
Pokaż odpowiedź
int maks = INT_MIN;
vector<int> v = {-8, -3, -6};
for (auto x : v) maks = max(maks, x);
cout << maks;
Pokaż odpowiedź
int n = 50731, mn = 9;
while (n > 0) {
mn = min(mn, n % 10);
n /= 10;
}
cout << mn;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Gdzie był rekord, ile razy padł i kto go ustanowił
Samo max odpowiada tylko na pytanie „ile?”. Zadania często pytają o więcej: na której pozycji stoi największa liczba? Kto zdobył najwięcej punktów? Ile osób ma najlepszy wynik? Do tego potrzebny jest zwykły if, w którym razem z rekordem zapamiętujesz dodatkowe informacje. W tej części nauczysz się też panować nad remisami — sytuacją, gdy rekord występuje kilka razy.
Pozycja rekordu
Wracamy do sędziego: tym razem zapisuje nie tylko długość najlepszego skoku, ale też jego numer. Gdy pada nowy rekord, zmieniają się obie rzeczy naraz — dlatego zamiast max używamy if z dwiema instrukcjami w klamrach.
int n;
cin >> n;
int maks, poz = 1;
cin >> maks; // pierwsza liczba ma pozycję 1
for (int i = 2; i <= n; i++) { // pozycje liczymy od 1
int x;
cin >> x;
if (x > maks) {
maks = x;
poz = i;
}
}
cout << maks << " na pozycji " << poz << "\n";
Zadania zwykle numerują pozycje od 1 („pierwsza liczba, druga liczba…”), a vector i tablica — od 0. Ten program wczytuje liczby bez vectora, więc po prostu liczy pozycje od 1. Gdy dane są w vectorze, pamiętaj o + 1 przy wypisywaniu.
Ósemka występuje dwa razy, a program podał pozycję 2 — pierwsze wystąpienie. Dlaczego? Bo przy drugiej ósemce warunek 8 > 8 jest fałszywy i rekord się nie zmienia.
Pierwsze czy ostatnie wystąpienie? > kontra >=
Jeden znak decyduje, które z równych wystąpień rekordu wygra. Z ostrym > rekord zmienia się tylko na lepszy, więc zostaje pierwsze wystąpienie. Z >= rekord zmienia się także na równy, więc każde kolejne wystąpienie nadpisuje poprzednie i zostaje ostatnie.
vector<int> v = {3, 8, 5, 8, 2};
int m1 = v[0], p1 = 0; // z >
int m2 = v[0], p2 = 0; // z >=
for (int i = 1; i < 5; i++) {
if (v[i] > m1) { m1 = v[i]; p1 = i; }
if (v[i] >= m2) { m2 = v[i]; p2 = i; }
}
cout << "pierwsza: " << p1 + 1 << "\n";
cout << "ostatnia: " << p2 + 1 << "\n";
| i | v[i] | z > | z >= |
|---|---|---|---|
| 1 | 8 | 8 > 3 → p1 = 1 | 8 >= 3 → p2 = 1 |
| 2 | 5 | nie | nie |
| 3 | 8 | 8 > 8? nie | 8 >= 8 → p2 = 3 |
| 4 | 2 | nie | nie |
> dla maksimum, < dla minimum) — wygrywa pierwsze wystąpienie. Znak z równością (>=, <=) — wygrywa ostatnie. Zawsze sprawdź w treści, którego wystąpienia chce zadanie.
Ile razy pojawia się rekord?
Prosty sposób to dwie pętle: pierwsza znajduje rekord, druga liczy, ile liczb jest mu równych. Da się to jednak zrobić w jednej pętli, z licznikiem ile. Gdy pada nowy rekord, licznik zaczyna od 1 — stare wystąpienia gorszego rekordu już się nie liczą. Gdy liczba wyrównuje rekord, licznik rośnie.
vector<int> v = {3, 8, 5, 8, 2, 8};
int maks = v[0], ile = 1;
for (int i = 1; i < (int)v.size(); i++) {
if (v[i] > maks) {
maks = v[i];
ile = 1; // nowy rekord — liczymy od nowa
} else if (v[i] == maks) {
ile++; // wyrównany rekord
}
}
cout << maks << " wystepuje " << ile << " razy\n";
Prześledź: start maks = 3, ile = 1. Ósemka bije trójkę — maks = 8, ile = 1 (ta jedna trójka przestaje się liczyć). Piątka nic nie zmienia. Druga ósemka wyrównuje — ile = 2. Dwójka nic. Trzecia ósemka — ile = 3.
Najczęstszy błąd: zapomnieć o ile = 1 przy nowym rekordzie. Wtedy licznik pamięta wyrównania starego, gorszego rekordu.
Kto ma rekord?
Wyniki zawodów to zwykle pary: imię i punkty. Zwycięzcę znajdziesz tym samym schematem — obok rekordu punktów trzymasz imię osoby, która go ustanowiła.
int n;
cin >> n;
string kto;
int najw;
cin >> kto >> najw; // pierwszy zawodnik
for (int i = 1; i < n; i++) {
string imie;
int pkt;
cin >> imie >> pkt;
if (pkt > najw) {
najw = pkt;
kto = imie;
}
}
cout << kto << " " << najw << "\n";
Kuba i Ewa mają po 23 punkty. Wygrał Kuba, bo był pierwszy, a Ewa tylko wyrównała jego wynik (23 > 23 to fałsz). Gdyby zadanie mówiło „przy remisie wygrywa osoba wpisana później”, wystarczyłoby >=.
A gdyby przy remisie miała wygrać osoba, której imię jest wcześniej w alfabecie? Wtedy warunek rośnie: pkt > najw || (pkt == najw && imie < kto).
Rekord według własnej miary: najbliżej celu
Czasem „najlepsza” nie znaczy „największa”. W zgadywance wygrywa liczba najbliżej celu. Odległość liczby x od celu to abs(x - cel) (z lekcji o parach: abs zabiera minus). Szukamy więc najmniejszej odległości, a przy remisie — powiedzmy — mniejszej liczby.
int cel = 50;
vector<int> v = {38, 61, 44, 56, 70};
int naj = v[0];
for (auto x : v) {
int d = abs(x - cel), dn = abs(naj - cel);
if (d < dn || (d == dn && x < naj)) naj = x;
}
cout << naj << "\n";
// to samo parami (odległość, liczba) — porównują się same
pair<int, int> p = {abs(v[0] - cel), v[0]};
for (auto x : v) p = min(p, make_pair(abs(x - cel), x));
cout << p.second << "\n";
| x | abs(x − 50) |
|---|---|
| 38 | 12 |
| 61 | 11 |
| 44 | 6 — remis |
| 56 | 6 — remis |
| 70 | 20 |
44 i 56 są tak samo blisko, wygrywa mniejsza: 44. Wersja z parami robi to samo krócej — pary porównują się najpierw po odległości, a przy remisie po samej liczbie. Znasz to z lekcji o parach.
Wszystkie miejsca rekordu
Gdy zadanie chce wszystkich pozycji, na których stoi największa liczba, najprościej zrobić dwa przejścia: najpierw znaleźć rekord, a potem jeszcze raz przejść po danych i wypisać numery liczb równych rekordowi. Do tego dane muszą być w vectorze — drugi raz z wejścia ich nie wczytasz.
vector<int> v = {4, 9, 2, 9, 9, 1};
int maks = v[0];
for (auto x : v) maks = max(maks, x); // przejście 1
for (int i = 0; i < (int)v.size(); i++) { // przejście 2
if (v[i] == maks) cout << i + 1 << " ";
}
cout << "\n";
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {5, 1, 5, 3};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
if (v[i] > m) { m = v[i]; p = i; }
cout << p;
Pokaż odpowiedź
vector<int> v = {5, 1, 5, 3};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
if (v[i] >= m) { m = v[i]; p = i; }
cout << p;
Pokaż odpowiedź
>= druga piątka wyrównuje rekord i nadpisuje pozycję.vector<int> v = {4, 2, 7, 2};
int m = v[0], p = 0;
for (int i = 1; i < 4; i++)
if (v[i] < m) { m = v[i]; p = i; }
cout << m << " " << p;
Pokaż odpowiedź
< zostaje pierwsze wystąpienie: pozycja 1.vector<int> v = {6, 2, 6, 6, 3};
int m = v[0], ile = 1;
for (int i = 1; i < 5; i++) {
if (v[i] > m) { m = v[i]; ile = 1; }
else if (v[i] == m) ile++;
}
cout << ile;
Pokaż odpowiedź
vector<string> im = {"Ala", "Bob", "Cyd"};
vector<int> pkt = {7, 9, 9};
int b = 0;
for (int i = 1; i < 3; i++)
if (pkt[i] > pkt[b]) b = i;
cout << im[b];
Pokaż odpowiedź
ile = 1. Co wypisze program?vector<int> v = {2, 2, 5};
int m = v[0], ile = 1;
for (int i = 1; i < 3; i++) {
if (v[i] > m) m = v[i];
else if (v[i] == m) ile++;
}
cout << m << " " << ile;
Pokaż odpowiedź
int cel = 10, naj = 7;
vector<int> v = {7, 13, 12};
for (auto x : v)
if (abs(x - cel) < abs(naj - cel)) naj = x;
cout << naj;
Pokaż odpowiedź
vector<int> v = {9, 4, 4};
pair<int, int> b = {v[0], 0};
for (int i = 0; i < 3; i++) b = min(b, make_pair(v[i], i));
cout << b.first << " " << b.second;
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
max_element i min_element — rekord bez pętli
Gdy dane siedzą już w vectorze, tablicy albo napisie, pętli z rekordem nie musisz pisać sam. C++ ma gotowe polecenia max_element i min_element, które poznałeś przelotnie w lekcji o vectorze. Teraz przyjrzymy się im dokładnie: jak odczytać z nich wartość i pozycję, jak użyć ich na tablicy, na kawałku danych i na napisie, jak znaleźć oba skrajne elementy naraz i jak szukać rekordu według własnej reguły.
Strzałka na rekord
max_element(v.begin(), v.end()) przegląda vector od pierwszej strzałki do drugiej i oddaje strzałkę (iterator) na największy element — nie samą liczbę. Ze strzałki wyciągasz dwie rzeczy, tak jak w lekcji o vectorze: gwiazdka * daje wartość, na którą strzałka pokazuje, a odjęcie v.begin() daje numer pudełka. Gdy największych jest kilka, strzałka pokazuje pierwszy z nich.
vector<int> v = {4, 9, 2, 9, 1};
cout << *max_element(v.begin(), v.end()) << "\n"; // wartość
cout << *min_element(v.begin(), v.end()) << "\n";
cout << max_element(v.begin(), v.end()) - v.begin() << "\n"; // numer
cout << min_element(v.begin(), v.end()) - v.begin() << "\n";
Pierwsze dwa wiersze to wartości: największa 9, najmniejsza 1.
Dwa kolejne to numery pudełek, liczone od 0: dziewiątka stoi w pudełku 1, jedynka w pudełku 4. Jeśli zadanie numeruje pozycje od 1, dodaj 1.
Bez gwiazdki cout nie wypisze wartości — strzałka to nie liczba i program się nie skompiluje.
Tablica, kawałek i napis
Te same polecenia działają na zwykłej tablicy — z tymi samymi strzałkami co w sort(t, t + n): max_element(t, t + n). Numer dostajesz wtedy, odejmując t. Działają też na kawałku danych: strzałki nie muszą obejmować całości. I działają na napisie, bo napis to rząd znaków.
int t[6] = {7, -3, 12, 5, 12, 0};
int n = 6;
cout << *max_element(t, t + n) << " " << *min_element(t, t + n) << "\n";
cout << max_element(t, t + n) - t << "\n"; // numer w tablicy
vector<int> v = {8, 1, 6, 3, 9, 2};
int a = 1, b = 3; // pudełka 1..3
cout << *max_element(v.begin() + a, v.begin() + b + 1) << "\n";
cout << max_element(v.begin() + a, v.begin() + b + 1) - v.begin() << "\n";
string s = "programowanie";
cout << *max_element(s.begin(), s.end()) << *min_element(s.begin(), s.end()) << "\n";
W tablicy 12 występuje dwa razy — numer 2 to pierwsze wystąpienie.
Kawałek od pudełka 1 do 3 to liczby 1, 6, 3. Największa jest szóstka. Uwaga: numer liczymy od v.begin(), a nie od początku kawałka, więc dostajemy prawdziwy numer pudełka w vectorze — 2. Druga strzałka ma + 1, bo pokazuje miejsce, którego już nie bierzemy.
W napisie „programowanie” najdalej w alfabecie jest litera w, a najwcześniej a.
Ile razy? count na pomoc
Z lekcji o vectorze znasz też count(v.begin(), v.end(), x) — liczy, ile razy x występuje w vectorze. Razem z max_element daje odpowiedź na pytanie z części 4 w dwóch linijkach:
vector<int> v = {3, 7, 7, 1, 7};
int mx = *max_element(v.begin(), v.end());
cout << mx << " x" << count(v.begin(), v.end(), mx) << "\n";
To dwa przejścia po danych (jedno w max_element, drugie w count), ale kod jest krótki i trudno się w nim pomylić. Przy danych do kilkuset tysięcy liczb to żaden problem.
Oba naraz: minmax_element
minmax_element w jednym przejściu znajduje oba skrajne elementy i oddaje parę strzałek: first pokazuje najmniejszy, a second największy. Parę wygodnie rozpakować tak jak w lekcji o parach: auto [lo, hi] = …. Jest jeden haczyk, który warto znać: przy remisie lo pokazuje pierwszy najmniejszy, ale hi — ostatni największy.
vector<int> v = {5, 1, 9, 1, 9};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << *lo << " " << *hi << "\n";
cout << lo - v.begin() << " " << hi - v.begin() << "\n";
Najmniejsza jedynka: pierwsza, z pudełka 1. Największa dziewiątka: ostatnia, z pudełka 4 — a nie z pudełka 2, jak przy max_element. Jeśli w zadaniu liczy się pozycja, sprawdź, którego wystąpienia potrzebujesz.
Rekord według własnej reguły
Pamiętasz z lekcji o sortowaniu regułę porównania — lambdę, która odpowiada na pytanie „czy a jest przed b?”. max_element i min_element też ją przyjmują jako trzeci argument. Reguła odpowiada wtedy na pytanie „czy a jest mniejsze od b?” — dokładnie tak samo jak w sort. Najdłuższe słowo? Reguła: „a jest mniejsze od b, gdy jest krótsze”.
vector<string> w = {"kot", "zebra", "pies", "tygrys", "jaguar"};
auto it = max_element(w.begin(), w.end(), [](string a, string b) {
return a.size() < b.size(); // krótsze = mniejsze
});
cout << *it << " " << it - w.begin() << "\n";
vector<int> v = {-7, 3, 5, -2};
cout << *max_element(v.begin(), v.end(), [](int a, int b) {
return abs(a) < abs(b); // dalej od zera = większe
}) << "\n";
„tygrys” i „jaguar” mają po 6 liter. Wygrywa pierwszy z nich — max_element zawsze oddaje pierwszy z równych.
W drugim przykładzie „największa” jest liczba najdalej od zera, czyli o największej wartości bezwzględnej: −7.
Reguła musi zwracać false dla równych elementów, więc piszemy <, nigdy <= — zasada z lekcji o sortowaniu.
Pętla czy gotowiec?
| sytuacja | co wybrać |
|---|---|
| liczby wczytujesz po kolei i nie musisz ich pamiętać | pętla z rekordem — nie trzeba vectora |
| dane są w vectorze, tablicy albo napisie, chcesz wartości albo numeru | max_element / min_element |
| potrzebujesz kilku rzeczy naraz (rekord, kto, ile razy, druga największa…) | pętla z if — pełna kontrola |
| „największy” według własnej miary | max_element z regułą albo pętla z parą |
max_element oddaje v.end() — strzałkę za ostatnim elementem, za którym nic nie ma. Gwiazdka przeczyta wtedy śmieci spoza vectora (tak jak v[0] w pustym vectorze). Jeśli dane mogą być puste, sprawdź to najpierw: if (v.empty()).
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {3, 8, 1};
cout << *max_element(v.begin(), v.end());
Pokaż odpowiedź
vector<int> v = {3, 8, 1, 1};
cout << min_element(v.begin(), v.end()) - v.begin();
Pokaż odpowiedź
int t[5] = {2, 9, 4, 9, 0};
cout << max_element(t, t + 5) - t;
Pokaż odpowiedź
int t[4] = {1, 5, 2, 8};
cout << *max_element(t, t + 3);
Pokaż odpowiedź
string s = "Ala";
cout << *max_element(s.begin(), s.end());
Pokaż odpowiedź
vector<int> v = {2, 2, 5, 5};
auto [lo, hi] = minmax_element(v.begin(), v.end());
cout << lo - v.begin() << " " << hi - v.begin();
Pokaż odpowiedź
vector<int> v = {4, -9, 6};
cout << *min_element(v.begin(), v.end(), [](int a, int b) {
return abs(a) < abs(b);
});
Pokaż odpowiedź
vector<int> v = {1, 4, 4, 2};
cout << count(v.begin(), v.end(), *max_element(v.begin(), v.end()));
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Nie mniej niż, nie więcej niż — przycinanie i przedziały
Do tej pory max i min szukały rekordów. Teraz poznasz ich drugie, równie częste zastosowanie: pilnowanie granic. Punkty życia w grze nie spadają poniżej zera, bateria nie naładuje się ponad 100%, a szklanka nie pomieści więcej wody, niż ma pojemności. Każde takie „nie mniej niż” i „nie więcej niż” to jedno max albo min. Na koniec użyjemy tego samego pomysłu do przedziałów: gdzie zaczyna się i kończy ich wspólna część.
Podłoga: max(0, x)
Postać w grze ma 30 punktów życia i dostaje 45 obrażeń. Ile ma życia? Matematycznie 30 − 45 = −15, ale w grze nie ma ujemnego życia — jest zero. Zapis max(0, hp - obrazenia) robi z zera podłogę: jeśli wynik jest dodatni, zostaje bez zmian; jeśli spadłby poniżej zera, max wybierze zero.
int hp = 30;
hp = max(0, hp - 12); // 18 — normalnie
cout << hp << "\n";
hp = max(0, hp - 45); // -27 → 0
cout << hp << "\n";
Czytaj max(0, x) jako „x, ale nie mniej niż 0”. To samo zrobiłbyś if-em: if (hp < 0) hp = 0; — ale tu wszystko mieści się w jednej linijce z odejmowaniem.
Podłoga nie musi być zerem. „Ocena nie niższa niż 1” to max(1, ocena).
Sufit: min(limit, x)
W drugą stronę działa min. Bateria ma 85% i ładujesz ją o 30 punktów procentowych — nie będzie 115%, tylko 100%. Zapis min(100, bateria + 30) robi z setki sufit: „bateria + 30, ale nie więcej niż 100”.
Sufit przydaje się też, gdy coś ma ograniczoną pojemność. Przelewasz wodę z dzbanka do szklanki: przeleje się tyle, ile jest w dzbanku, ale nie więcej, niż zmieści się w szklance. Ile się zmieści? Pojemność minus to, co już jest w środku.
int bateria = 85;
bateria = min(100, bateria + 30);
cout << bateria << "\n";
int dzbanek = 700, szklanka = 150, pojemnosc = 250;
int ile = min(dzbanek, pojemnosc - szklanka); // ile się przeleje
dzbanek -= ile;
szklanka += ile;
cout << ile << " " << dzbanek << " " << szklanka << "\n";
W szklance jest 150 ml, a mieści się 250 ml, więc wolnego miejsca jest 100 ml. W dzbanku jest dużo więcej (700 ml), więc przelewa się tylko 100 ml i szklanka jest pełna.
Gdyby w dzbanku było tylko 60 ml, min(60, 100) dałoby 60 — przelałaby się cała woda z dzbanka.
Podłoga i sufit naraz: przycinanie
Gdy wartość ma się mieścić między dwiema granicami — od lo do hi — składamy oba pomysły: max(lo, min(hi, x)). Czytamy od środka: min(hi, x) ścina wszystko powyżej górnej granicy, a max(lo, …) podnosi wszystko poniżej dolnej. Takie działanie nazywa się przycinaniem (po angielsku clamp), i od C++17 jest na nie gotowa funkcja clamp(x, lo, hi). Uwaga na kolejność: w clamp najpierw idzie wartość, potem dolna i górna granica.
vector<int> zmiany = {150, -30, 42, 100, 0};
for (int x : zmiany) {
int a = max(0, min(100, x));
int b = clamp(x, 0, 100); // to samo gotowcem
cout << x << " -> " << a << " " << b << "\n";
}
| x | min(100, x) | max(0, …) |
|---|---|---|
| 150 | 100 | 100 |
| −30 | −30 | 0 |
| 42 | 42 | 42 |
Fioletowe wartości to miejsca, w których granica „zadziałała”. Liczba 42 mieści się w przedziale, więc przechodzi bez zmian.
min(0, max(100, x)). Wtedy max(100, x) daje co najmniej 100, a min(0, …) zawsze 0 — każda liczba zamienia się w zero. Zapamiętaj: przy dolnej granicy stoi max (podłoga podnosi), przy górnej — min (sufit obniża).
Wspólna część dwóch przedziałów
Ola ma czas od 14 do 18, a Kuba od 16 do 20. Kiedy oboje mają czas? Wspólna część zaczyna się wtedy, gdy oboje już zaczęli — czyli w późniejszym z początków: max(14, 16) = 16. Kończy się, gdy ktoś pierwszy skończy — we wcześniejszym z końców: min(18, 20) = 18. Jeśli wyszło, że początek jest za końcem, wspólnej części nie ma. Znasz to już z lekcji o parach — teraz policzymy jeszcze jej długość.
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
int od = max(a1, a2);
int doo = min(b1, b2);
cout << "od " << od << " do " << doo << "\n";
cout << "dlugosc: " << max(0, doo - od) << "\n";
Za drugim razem przedziały [2, 5] i [8, 12] się rozmijają: „wspólna część” od 8 do 5 nie istnieje, bo zaczyna się za swoim końcem. Długość 5 − 8 = −3 nie ma sensu — i tu znowu pomaga podłoga: max(0, doo - od) zamienia każdą ujemną długość na zero.
Zmienna nazywa się doo, bo do jest w C++ zajęte — to słowo z pętli do … while.
max początków. Koniec: min końców. Długość: max(0, koniec - początek). Dla wielu przedziałów naraz: początek to największy ze wszystkich początków, koniec — najmniejszy ze wszystkich końców (czyli dwa rekordy w jednej pętli).
Dwa prostokąty na planszy
Ten sam pomysł działa w dwóch wymiarach. Prostokąt o bokach równoległych do osi to po prostu dwa przedziały: jeden na osi x (od lewej do prawej krawędzi) i jeden na osi y (od dołu do góry). Część wspólna dwóch prostokątów to prostokąt, którego szerokość jest wspólną częścią przedziałów x, a wysokość — wspólną częścią przedziałów y. Pole = szerokość · wysokość.
// prostokąt: lewy dolny róg (x1, y1), prawy górny (x2, y2)
long long ax1 = 0, ay1 = 0, ax2 = 6, ay2 = 4; // prostokąt A
long long bx1 = 3, by1 = 2, bx2 = 9, by2 = 7; // prostokąt B
long long szer = max(0LL, min(ax2, bx2) - max(ax1, bx1));
long long wys = max(0LL, min(ay2, by2) - max(ay1, by1));
cout << szer << " " << wys << " " << szer * wys << "\n";
Na osi x: [0, 6] i [3, 9] mają wspólne [3, 6], czyli szerokość 3. Na osi y: [0, 4] i [2, 7] mają wspólne [2, 4], czyli wysokość 2. Pole wspólnej części: 3 · 2 = 6.
Używamy long long, bo współrzędne mogą być duże, a pole to iloczyn. Stąd 0LL w max — zasada jednego typu.
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
int hp = 20;
hp = max(0, hp - 7);
hp = max(0, hp - 15);
cout << hp;
Pokaż odpowiedź
int b = 90;
b = min(100, b + 5);
b = min(100, b + 5);
b = min(100, b + 5);
cout << b;
Pokaż odpowiedź
cout << clamp(17, 0, 10) << " " << clamp(-3, 0, 10);
Pokaż odpowiedź
int x = 55;
cout << max(10, min(50, x));
Pokaż odpowiedź
int x = 42;
cout << min(0, max(100, x));
Pokaż odpowiedź
int a1 = 3, b1 = 10, a2 = 7, b2 = 15;
cout << max(0, min(b1, b2) - max(a1, a2));
Pokaż odpowiedź
int a1 = 1, b1 = 4, a2 = 6, b2 = 9;
cout << max(0, min(b1, b2) - max(a1, a2));
Pokaż odpowiedź
int dzbanek = 40, szklanka = 180, poj = 250;
cout << min(dzbanek, poj - szklanka);
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Dwie największe w jednym przejściu
Na zawodach nie liczy się tylko zwycięzca — jest też drugie i trzecie miejsce. Jak znaleźć drugą największą liczbę? Jeden sposób już znasz: posortować malejąco i wziąć v[1]. Działa, ale miesza kolejność danych i wymaga trzymania ich wszystkich w vectorze. W tej części poznasz sposób bez sortowania: dwa rekordy naraz, które w jednym przejściu pilnują złota i srebra. Potem użyjemy go do najlepszej pary, największego iloczynu i całego podium.
Złoto i srebro: m1 i m2
Trzymamy dwie zmienne: m1 — największa liczba do tej pory (złoto) i m2 — druga największa (srebro). Przychodzi nowa liczba x. Są trzy możliwości:
1) x jest większa od złota — nowa mistrzyni! Dotychczasowe złoto nie znika, tylko spada na srebro: najpierw m2 = m1, dopiero potem m1 = x.
2) x nie bije złota, ale jest większa od srebra — zabiera srebro: m2 = x.
3) x nie bije nikogo — nic się nie zmienia.
int n;
cin >> n;
int m1 = INT_MIN, m2 = INT_MIN; // złoto i srebro
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > m1) {
m2 = m1; // stare złoto spada na srebro
m1 = x;
} else if (x > m2) {
m2 = x;
}
}
cout << m1 << " " << m2 << "\n";
| x | co się dzieje | m1 | m2 |
|---|---|---|---|
| 12 | bije złoto (INT_MIN) | 12 | INT_MIN |
| 45 | bije złoto — 12 spada | 45 | 12 |
| 7 | nikogo nie bije | 45 | 12 |
| 45 | nie bije złota, bije srebro | 45 | 45 |
| 30 | nikogo nie bije | 45 | 45 |
| 51 | bije złoto — 45 spada | 51 | 45 |
| 8 | nikogo nie bije | 51 | 45 |
m1 = x; m2 = m1;, to w drugiej linijce m1 jest już nowe — i obie zmienne dostają x. Stare złoto przepada. Zawsze najpierw przesuwaj w dół (m2 = m1), a dopiero potem wpisuj nową wartość na górę.
Druga największa — licząc powtórzenia czy nie?
Dla liczb 9, 9, 5 program powyżej odpowie: m1 = 9, m2 = 9. Czy to dobrze? To zależy od treści zadania. Jeśli pyta o „dwie największe liczby z listy” (np. dwa najlepsze wyniki) — tak, druga dziewiątka to osobny wynik. Jeśli pyta o „drugą największą wartość” albo „drugą największą różną liczbę” — odpowiedź to 5. Wtedy liczbę równą złotu trzeba pominąć: srebro dostaje tylko liczba mniejsza od złota.
vector<int> v = {9, 9, 5};
int m1 = INT_MIN, m2 = INT_MIN; // z powtórzeniami
int r1 = INT_MIN, r2 = INT_MIN; // różne wartości
for (auto x : v) {
if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
if (x > r1) { r2 = r1; r1 = x; }
else if (x < r1 && x > r2) r2 = x; // równa złotu — pomijamy
}
cout << m1 << " " << m2 << "\n";
cout << r1 << " " << r2 << "\n";
Różnica jest tylko w jednym warunku: x < r1 && x > r2. Druga dziewiątka nie jest mniejsza od złota, więc nie wchodzi na srebro.
A jeśli wszystkie liczby są równe? Wtedy różnej drugiej wartości po prostu nie ma — r2 zostaje równe INT_MIN i po tym poznasz, że trzeba wypisać na przykład BRAK.
Najlepsza para: suma i iloczyn
Największa suma dwóch różnych elementów to po prostu m1 + m2 — dwie największe liczby razem. Z iloczynem jest ciekawiej, bo minus razy minus daje plus. Dwie bardzo „duże” liczby ujemne, np. −10 i −8, dają iloczyn 80, większy niż iloczyn dwóch największych dodatnich. Dlatego kandydatów jest dwóch: iloczyn dwóch największych i iloczyn dwóch najmniejszych. Wynikiem jest większy z nich.
vector<long long> v = {-10, -8, 1, 3, 5};
long long m1 = LLONG_MIN, m2 = LLONG_MIN; // dwie największe
long long s1 = LLONG_MAX, s2 = LLONG_MAX; // dwie najmniejsze
for (auto x : v) {
if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
if (x < s1) { s2 = s1; s1 = x; }
else if (x < s2) s2 = x;
}
cout << "suma: " << m1 + m2 << "\n";
cout << "iloczyn: " << max(m1 * m2, s1 * s2) << "\n";
Dwie największe: 5 i 3 — suma 8, iloczyn 15. Dwie najmniejsze: −10 i −8 — iloczyn 80. Wygrywa 80.
Dwie najmniejsze szukamy tym samym schematem, tylko ze znakiem < i startem od LLONG_MAX.
Iloczyn dwóch liczb rzędu miliarda to już 1018 — dlatego long long.
Całe podium: trzy największe
Schemat rozszerza się na trzy miejsca bez nowych pomysłów — jest tylko dłuższy łańcuch przesunięć. Gdy x bije złoto, wszyscy spadają o jedno miejsce: brąz dostaje srebro, srebro dostaje złoto. Gdy bije tylko srebro — przesuwa się srebro na brąz. Gdy bije tylko brąz — zabiera brąz.
vector<int> v = {40, 75, 62, 90, 75, 18};
int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
for (auto x : v) {
if (x > m1) { m3 = m2; m2 = m1; m1 = x; }
else if (x > m2) { m3 = m2; m2 = x; }
else if (x > m3) { m3 = x; }
}
cout << m1 << " " << m2 << " " << m3 << "\n";
Przy dwóch, trzech miejscach takie rekordy są wygodne i szybkie. Gdy zadanie pyta o dziesięć najlepszych albo o k-tą największą liczbę dla dowolnego k, łańcuch zrobiłby się za długi — wtedy wracamy do sortowania z poprzedniej lekcji: sort malejąco i v[k - 1].
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {5, 9, 7};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
int m1 = 1, m2 = 0;
int x = 8;
if (x > m1) { m1 = x; m2 = m1; }
cout << m1 << " " << m2;
Pokaż odpowiedź
vector<int> v = {6, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
vector<int> v = {6, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN;
for (auto x : v) {
if (x > m1) { m2 = m1; m1 = x; }
else if (x < m1 && x > m2) m2 = x;
}
cout << m1 << " " << m2;
Pokaż odpowiedź
long long a = 2 * 1, b = (-5) * (-4);
cout << max(a, b);
Pokaż odpowiedź
vector<int> v = {7, 3, 9, 3};
int s1 = INT_MAX, s2 = INT_MAX;
for (auto x : v) {
if (x < s1) { s2 = s1; s1 = x; }
else if (x < s2) s2 = x;
}
cout << s1 + s2;
Pokaż odpowiedź
vector<int> v = {4, 1, 8, 6, 2};
int m1 = INT_MIN, m2 = INT_MIN, m3 = INT_MIN;
for (auto x : v) {
if (x > m1) { m3 = m2; m2 = m1; m1 = x; }
else if (x > m2) { m3 = m2; m2 = x; }
else if (x > m3) m3 = x;
}
cout << m3;
Pokaż odpowiedź
vector<int> v = {3, 9, 9, 1};
sort(v.rbegin(), v.rend());
cout << v[1];
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Rekordy na bieżąco, widok z prawej i najlepszy zysk
Do tej pory rekord był ważny dopiero na końcu, po obejrzeniu wszystkich liczb. A przecież w trakcie pętli on też coś znaczy: po każdym kroku mówi, jaki jest rekord do tej pory. W tej części wykorzystamy te pośrednie wartości: wypiszemy rekordy dzień po dniu, policzymy, ile razy rekord został pobity, spojrzymy na dane od prawej strony, a na koniec rozwiążemy słynne zadanie o kupnie i sprzedaży akcji.
Rekord dzień po dniu
Biegacz notuje wyniki kolejnych treningów (powiedzmy, ile kilometrów przebiegł). Po każdym treningu chce wiedzieć, jaki jest jego rekord życiowy i czy właśnie go pobił. Wystarczy wypisywać rekord w środku pętli, po każdej aktualizacji. Taki ciąg rekordów nazywa się maksimum prefiksowym — prefiks to początek ciągu, a my po każdym kroku znamy maksimum początku od pierwszej liczby do bieżącej.
int n;
cin >> n;
int rekord = INT_MIN, ile = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x > rekord) ile++; // rekord pobity!
rekord = max(rekord, x);
cout << rekord << " "; // rekord do tej pory
}
cout << "\n";
cout << "rekord bity " << ile << " razy\n";
Pierwszy wynik zawsze jest rekordem — dlatego start od INT_MIN: pierwsza liczba na pewno go pobije i zostanie policzona.
Rekord padał przy 3, 7, 9 i 12. Druga dziewiątka tylko go wyrównała (9 > 9 to fałsz), więc się nie liczy.
Zauważ, że wypisany ciąg nigdy nie maleje — rekord może tylko rosnąć albo stać w miejscu.
Tablica rekordów: od lewej i od prawej
Czasem rekordy trzeba nie tylko wypisać, ale zapamiętać, żeby później z nich korzystać. Wtedy zapisujemy je do vectora pm: pm[i] to największa liczba wśród a[0]…a[i]. Każdy kolejny element liczymy z poprzedniego: pm[i] = max(pm[i - 1], a[i]). Tak samo da się iść od prawej: sm[i] to największa liczba wśród a[i]…a[n - 1], a liczymy ją pętlą od końca: sm[i] = max(sm[i + 1], a[i]).
vector<int> a = {3, 7, 5, 9, 4, 2};
int n = a.size();
vector<int> pm(n), sm(n);
pm[0] = a[0];
for (int i = 1; i < n; i++) pm[i] = max(pm[i - 1], a[i]);
sm[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) sm[i] = max(sm[i + 1], a[i]);
for (auto x : pm) cout << x << " ";
cout << "\n";
for (auto x : sm) cout << x << " ";
cout << "\n";
Po co to? Mając obie tablice, dla każdego miejsca i od razu wiesz, jaka jest największa liczba na lewo i na prawo od niego — bez przeglądania danych od nowa. To ważne: gdybyś dla każdego i szukał maksimum osobną pętlą, wyszłaby pętla w pętli, czyli około n·n kroków. Z tablicami pm i sm to tylko trzy zwykłe pętle.
Widok z prawej
W rzędzie stoją budynki o różnych wysokościach. Patrzysz na nie z prawej strony, z bardzo daleka. Który budynek widzisz? Ten, który jest wyższy od wszystkich budynków na prawo od niego — niższe zasłania coś bliżej Ciebie. Idziemy więc od prawej do lewej z rekordem maksPrawo (najwyższy budynek po prawej) i sprawdzamy, czy bieżący budynek go bije.
vector<int> h = {4, 9, 3, 7, 2, 5, 1};
int maksPrawo = INT_MIN, widac = 0;
for (int i = (int)h.size() - 1; i >= 0; i--) {
if (h[i] > maksPrawo) {
widac++;
cout << "widac budynek " << i + 1 << " (wysokosc " << h[i] << ")\n";
}
maksPrawo = max(maksPrawo, h[i]);
}
cout << widac << "\n";
To ten sam schemat co „rekord bity”, tylko pętla idzie od końca. Budynek jest widoczny dokładnie wtedy, gdy bije rekord liczony od prawej.
Najlepszy zysk: kup tanio, sprzedaj drogo
Znasz ceny akcji z n kolejnych dni. Możesz kupić jedną akcję w jednym dniu i sprzedać ją w którymś późniejszym. Jaki największy zysk da się osiągnąć? Sprawdzanie wszystkich par dni (kupno, sprzedaż) to pętla w pętli. Sprytniej: idziemy dzień po dniu i zakładamy, że sprzedajemy dzisiaj. Kiedy najlepiej było kupić? Oczywiście najtaniej — a najniższą cenę z dni wcześniejszych pamięta rekord mini. Zysk przy sprzedaży dziś to cena - mini, a najlepszy zysk to rekord tych wartości.
int n;
cin >> n;
int mini = INT_MAX, zysk = 0;
for (int i = 0; i < n; i++) {
int cena;
cin >> cena;
zysk = max(zysk, cena - mini); // 1. sprzedaż dziś
mini = min(mini, cena); // 2. potem dopisz dzisiejszą cenę
}
cout << zysk << "\n";
Najlepiej kupić w dniu 1 po 1 i sprzedać w dniu 4 po 6: zysk 5.
W drugich danych ceny tylko spadają — każda sprzedaż przyniosłaby stratę, więc najlepiej nie kupować wcale. Zysk 0 to start rekordu: „nic nie robię”.
Kolejność linijek w pętli ma znaczenie: najpierw liczymy sprzedaż, a dopiero potem dopisujemy dzisiejszą cenę do minimum. Dzięki temu kupno jest zawsze wcześniej niż sprzedaż. W pierwszym dniu cena - INT_MAX to wielka liczba ujemna, więc zysk się nie zmienia.
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {2, 1, 4, 3};
int r = INT_MIN;
for (auto x : v) {
r = max(r, x);
cout << r;
}
Pokaż odpowiedź
vector<int> v = {5, 5, 6, 1, 7};
int r = INT_MIN, ile = 0;
for (auto x : v) {
if (x > r) ile++;
r = max(r, x);
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {1, 3, 2};
vector<int> sm(3);
sm[2] = a[2];
for (int i = 1; i >= 0; i--) sm[i] = max(sm[i + 1], a[i]);
cout << sm[0] << sm[1] << sm[2];
Pokaż odpowiedź
vector<int> h = {3, 1, 2};
int mp = INT_MIN, w = 0;
for (int i = 2; i >= 0; i--) {
if (h[i] > mp) w++;
mp = max(mp, h[i]);
}
cout << w;
Pokaż odpowiedź
vector<int> c = {5, 3, 8, 1, 4};
int mini = INT_MAX, z = 0;
for (auto x : c) {
z = max(z, x - mini);
mini = min(mini, x);
}
cout << z;
Pokaż odpowiedź
vector<int> c = {9, 4, 2};
int mini = INT_MAX, z = 0;
for (auto x : c) {
z = max(z, x - mini);
mini = min(mini, x);
}
cout << z;
Pokaż odpowiedź
vector<int> a = {4, 8, 1, 2};
vector<int> pm(4);
pm[0] = a[0];
for (int i = 1; i < 4; i++) pm[i] = max(pm[i - 1], a[i]);
cout << pm[3];
Pokaż odpowiedź
vector<int> v = {6, 7, 3, 5};
int r = INT_MAX;
for (auto x : v) {
r = min(r, x);
cout << r;
}
Pokaż odpowiedź
7 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Najdłuższa seria, najlepsze okno i największa suma fragmentu
Ostatnia część lekcji to rekordy wśród fragmentów — kawałków ciągu złożonych z sąsiednich liczb. Najdłuższa seria wygranych, najcieplejsze trzy dni z rzędu, najlepszy kawałek drogi. We wszystkich tych zadaniach działa ten sam pomysł: idziemy po ciągu, trzymamy coś, co opisuje fragment kończący się w bieżącym miejscu, i robimy z tego rekord. Na koniec zobaczysz, jak szukać maksimów i minimów w tabeli dwuwymiarowej.
Najdłuższa seria: obecny i najlepszy
Seria to fragment, w którym wszystkie liczby są takie same. Trzymamy dwie zmienne: obecny — długość serii, w której właśnie jesteśmy, i najlepszy — rekord. Jeśli liczba jest taka sama jak poprzednia, seria trwa (obecny++). Jeśli inna — zaczyna się nowa seria o długości 1. Po każdym kroku poprawiamy rekord.
vector<int> v = {7, 7, 2, 2, 2, 5, 2, 2};
int obecny = 1, najlepszy = 1;
for (int i = 1; i < (int)v.size(); i++) {
if (v[i] == v[i - 1]) obecny++;
else obecny = 1;
najlepszy = max(najlepszy, obecny); // w KAŻDYM kroku
}
cout << najlepszy << "\n";
Najdłuższy rosnący fragment
Ten sam schemat, inny warunek: fragment trwa, dopóki każda liczba jest większa od poprzedniej. Gdy liczba nie jest większa, rosnący fragment się urywa, a ona sama zaczyna nowy. Tym razem liczby wczytujemy bez vectora — wystarczy pamiętać poprzednią.
int n;
cin >> n;
int poprz;
cin >> poprz;
int obecny = 1, najlepszy = 1;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
if (x > poprz) obecny++;
else obecny = 1;
najlepszy = max(najlepszy, obecny);
poprz = x; // teraz x jest „poprzednią”
}
cout << najlepszy << "\n";
Fragmenty rosnące: 3 5 8 (długość 3), 4 6 9 12 (długość 4) i 2 7 (długość 2). Najdłuższy ma 4.
Najważniejsza jest ostatnia linijka pętli: poprz = x. Bez niej program porównywałby każdą liczbę z pierwszą, a nie z poprzednią.
Najlepsze okno: k kolejnych liczb
Masz temperatury z n dni i chcesz znaleźć najcieplejsze k dni z rzędu — czyli k kolejnych liczb o największej sumie. Takie k kolejnych liczb to okno, które przesuwamy po danych o jedno miejsce. Liczenie sumy każdego okna od nowa to k dodawań na każde okno. Sprytniej: przy przesunięciu do okna wchodzi jedna liczba z prawej, a wychodzi jedna z lewej — więc suma zmienia się o t[i] - t[i - k].
vector<int> t = {2, 5, 1, 8, 7, 3, 4};
int k = 3;
int suma = 0;
for (int i = 0; i < k; i++) suma += t[i]; // pierwsze okno
int najl = suma, start = 0;
for (int i = k; i < (int)t.size(); i++) {
suma += t[i] - t[i - k]; // wchodzi t[i], wychodzi t[i - k]
if (suma > najl) {
najl = suma;
start = i - k + 1; // pierwsze pudełko nowego okna
}
}
cout << najl << " od pozycji " << start + 1 << "\n";
Gdy i = 3, do okna wchodzi t[3] = 8, a wychodzi t[0] = 2: suma 8 + 8 − 2 = 14. Tak, krok po kroku, dostajemy sumy wszystkich okien, wykonując w każdym kroku tylko dwa działania.
Okno kończy się w pudełku i, więc zaczyna w pudełku i - k + 1. Wypisujemy pozycję od 1, stąd + 1.
Największa suma fragmentu
A co, jeśli długość fragmentu jest dowolna? Liczby mogą być ujemne, więc nie opłaca się brać wszystkiego. Przykład: dla ciągu 2, −5, 3, 1, −2, 4, −6, 1 najlepszy kawałek to 3, 1, −2, 4 o sumie 6 — mimo że w środku jest −2. To zadanie ma piękne rozwiązanie w jednej pętli (w świecie programistów znane jako algorytm Kadane’a).
Pomysł: dla każdego miejsca i liczymy obecna — największą sumę fragmentu, który kończy się dokładnie w i. Taki fragment albo składa się z samej liczby x, albo jest najlepszym fragmentem kończącym się w i − 1 z doklejonym x. Wybieramy lepszą z tych dwóch możliwości: obecna = max(x, obecna + x). Innymi słowy: jeśli to, co mamy za sobą, ma sumę ujemną, lepiej to wyrzucić i zacząć od nowa. Wynikiem jest rekord wszystkich wartości obecna.
vector<long long> v = {2, -5, 3, 1, -2, 4, -6, 1};
long long obecna = v[0], najl = v[0];
for (int i = 1; i < (int)v.size(); i++) {
obecna = max(v[i], obecna + v[i]); // od nowa albo doklej
najl = max(najl, obecna);
}
cout << najl << "\n";
| x | max(x, obecna + x) | obecna | najl |
|---|---|---|---|
| 2 | start | 2 | 2 |
| −5 | max(−5, −3) | −3 | 2 |
| 3 | max(3, 0) — od nowa | 3 | 3 |
| 1 | max(1, 4) | 4 | 4 |
| −2 | max(−2, 2) | 2 | 4 |
| 4 | max(4, 6) | 6 | 6 |
| −6 | max(−6, 0) | 0 | 6 |
| 1 | max(1, 1) | 1 | 6 |
Start od v[0], a nie od zera, ma znaczenie, gdy wszystkie liczby są ujemne. Fragment musi mieć co najmniej jedną liczbę, więc dla −4, −2, −7 odpowiedzią jest −2 (sama dwójka), a nie 0. Sumy mogą być duże, dlatego long long.
Maksima i minima w tabeli
W tabeli dwuwymiarowej (vector vectorów z lekcji o vectorze) rekord można liczyć dla każdego wiersza, dla każdej kolumny albo dla całości. Ciekawy przykład: trzy trasy rowerowe, każda ma cztery podjazdy o różnej trudności. Trudność trasy to jej najtrudniejszy podjazd — maksimum wiersza. Chcemy wybrać trasę, która jest najłatwiejsza, czyli taką, której najtrudniejszy podjazd jest jak najłatwiejszy — najmniejsze z maksimów.
vector<vector<int>> t = {
{3, 8, 1, 6},
{7, 2, 9, 4},
{5, 5, 0, 8}};
int w = t.size(), k = t[0].size();
int najmZMaks = INT_MAX;
for (int i = 0; i < w; i++) {
int m = *max_element(t[i].begin(), t[i].end());
cout << "trasa " << i << ": " << m << "\n";
najmZMaks = min(najmZMaks, m);
}
cout << "najlatwiejsza: " << najmZMaks << "\n";
for (int j = 0; j < k; j++) { // maksimum każdej kolumny
int m = t[0][j];
for (int i = 1; i < w; i++) m = max(m, t[i][j]);
cout << m << " ";
}
cout << "\n";
Dla wiersza wygodnie użyć max_element, bo wiersz t[i] to zwykły vector. Kolumna nie jest vectorem — jej liczby leżą w różnych wierszach — więc tu potrzebna jest pętla po wierszach z rekordem.
To schemat „najlepszy z najgorszych”: najpierw w każdej grupie szukasz najgorszego przypadku (max), a potem wybierasz grupę z najlepszym najgorszym przypadkiem (min).
Najpierw odpowiedz w myślach — zapisz sobie na kartce zmienne (maks, mini…) i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {1, 1, 1, 2, 2};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
if (v[i] == v[i - 1]) ob++;
else ob = 1;
naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
vector<int> v = {4, 5, 5, 5, 5};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
if (v[i] == v[i - 1]) ob++;
else { naj = max(naj, ob); ob = 1; }
}
cout << naj;
Pokaż odpowiedź
vector<int> v = {1, 2, 2, 3, 4};
int ob = 1, naj = 1;
for (int i = 1; i < 5; i++) {
if (v[i] > v[i - 1]) ob++;
else ob = 1;
naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
vector<int> t = {4, 1, 3, 5};
int s = t[0] + t[1], b = s;
for (int i = 2; i < 4; i++) {
s += t[i] - t[i - 2];
b = max(b, s);
}
cout << b;
Pokaż odpowiedź
vector<int> v = {-2, 3, -1, 2};
int ob = v[0], naj = v[0];
for (int i = 1; i < 4; i++) {
ob = max(v[i], ob + v[i]);
naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
vector<int> v = {-4, -2, -7};
int ob = v[0], naj = v[0];
for (int i = 1; i < 3; i++) {
ob = max(v[i], ob + v[i]);
naj = max(naj, ob);
}
cout << naj;
Pokaż odpowiedź
vector<vector<int>> t = {{2, 9}, {6, 5}};
int r = INT_MAX;
for (auto w : t) r = min(r, max(w[0], w[1]));
cout << r;
Pokaż odpowiedź
vector<int> v = {1, -3, 2};
int ob = 0;
for (auto x : v) {
ob = max(x, ob + x);
cout << ob << " ";
}
Pokaż odpowiedź
8 ćwiczeń do tej części
Kliknij zadanie — otworzy się w sprawdzarce w nowej karcie. Napisz program u siebie, sprawdź go na przykładzie, wklej cały kod i kliknij Wyślij. Utknąłeś? Każde zadanie ma wskazówkę.
Baza zadań: max i min w praktyce
Znasz już wszystkie narzędzia: max i min dla dwóch liczb i dla listy w klamrach, zasadę jednego typu, rekord w pętli z dobrym startem, pozycję rekordu i remisy, liczenie wystąpień, max_element i min_element, przycinanie i wspólne części przedziałów, dwie i trzy największe liczby, rekordy na bieżąco od lewej i od prawej, najlepszy zysk, serie, okna i największą sumę fragmentu. Czas na zadania, które łączą kilka z tych rzeczy naraz. Są ułożone od najłatwiejszego do najtrudniejszego: najpierw rozgrzewka z jednym pomysłem, potem zadania średnie, w których łączysz dwa, trzy pomysły, a na końcu trudne — z wielkim finałem.
Przy każdym zadaniu widać, jakich zagadnień używa — także tych z poprzednich lekcji, jak napisy, pary, vector czy sortowanie. Jeśli coś brzmi obco, wróć do odpowiedniej części — mapa lekcji jest na górze strony. A tu masz najważniejsze schematy z lekcji w jednym miejscu:
Ściąga: gotowe schematy
Dwie i więcej liczb
max(a, b) min(a, b)
max({a, b, c, d})
a + b + c - mx - mn // środkowa
max(x, 0LL) // long long!
Oba argumenty tego samego typu: 3.0, 7LL, (int)s.size().
Rekord w pętli
int maks = pierwsza; // albo INT_MIN for (...) maks = max(maks, x); int mini = INT_MAX; for (...) mini = min(mini, x);
Nigdy od 0, gdy liczby mogą być ujemne. Rekord „tylko z niektórych” — z flagą bool jest.
Gdzie i ile razy
if (x > maks) { maks = x; poz = i; }
// > pierwsze, >= ostatnie
if (x > maks) { maks = x; ile = 1; }
else if (x == maks) ile++;
Kto ma rekord — zapamiętaj imię albo numer obok wartości.
Gotowce
*max_element(v.begin(), v.end()) max_element(...) - v.begin() // numer max_element(t, t + n) - t auto [lo, hi] = minmax_element(...);
Pierwsze wystąpienie (hi z minmax — ostatnie). Reguła jak w sort: [](a, b) { return … < …; }.
Granice
max(0, x) // podłoga min(limit, x) // sufit max(lo, min(hi, x)) // clamp(x, lo, hi) max(0, min(b1, b2) - max(a1, a2))
Wspólna część: max początków, min końców.
Podium
if (x > m1) { m2 = m1; m1 = x; }
else if (x > m2) m2 = x;
// różne: else if (x < m1 && x > m2)
max(m1 * m2, s1 * s2) // iloczyn
Najpierw przesuń w dół, potem wpisz na górę.
Na bieżąco
pm[i] = max(pm[i - 1], a[i]); sm[i] = max(sm[i + 1], a[i]); zysk = max(zysk, cena - mini); mini = min(mini, cena);
Para „wcześniej — później”: jedna pętla z rekordem zamiast dwóch pętli.
Serie i fragmenty
ob = (warunek) ? ob + 1 : 1; naj = max(naj, ob); // co krok! suma += t[i] - t[i - k]; // okno ob = max(x, ob + x); // Kadane
Sumy fragmentów bywają duże — long long.
max; najmniejszy, najkrótszy, najtańszy, najszybszy → min. 2) Ustal, czego jest rekord: samej liczby, czegoś policzonego (długości, odległości, sumy), a może fragmentu? 3) Wybierz start: pierwsza liczba, INT_MIN / INT_MAX albo flaga. 4) Sprawdź, co z remisami i czy trzeba podać pozycję — wtedy if z ostrym albo nieostrym znakiem. 5) Gdy w pomyśle pojawia się pętla w pętli, a n jest duże, poszukaj rekordu „na bieżąco”. 6) Przetestuj skrajności: jedna liczba, wszystkie równe, wszystkie ujemne, ogromne wartości (long long!).
Rozgrzewka · zadania 1–10
Jeden, dwa pomysły naraz: pogoda w maju, najszybszy biegacz, promocja 3 za 2, strata do lidera, fotoradar, najlepszy skok, dobowe wahania temperatury, ramka wokół punktów, bankomat i najdłuższa przerwa między autobusami.
Średnie · zadania 11–20
Kilka sztuczek naraz: najdziwniejszy wynik, dwie kasy w sklepie, najcieplejszy dzień każdego tygodnia, najlepszy moment na transakcję, iloczyn trzech liczb, puchar, wspólne pole prostokątów, spotkanie w połowie drogi, pogoda na wycieczkę oraz najlepszy wiersz i kolumna.
Trudne · zadania 21–28
Deszczówka, dwie transakcje, naszyjnik z koralików, najdłuższa górka, największy iloczyn fragmentu, ścieżka po planszy, ławka w parku — a na koniec wielki finał: wyprawa w góry.