Wolisz obejrzeć?
Olimpijskie Koło Informatyczne nagrywa swoje zajęcia i udostępnia je za darmo. Poniżej 6 odcinków o tym temacie — dobre uzupełnienie, jeśli wolisz obejrzeć niż przeczytać.
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 i Vector. Najbardziej przydadzą się dwie ostatnie: z lekcji o vectorze — strzałki begin() i end() oraz zakres [od, do), a z lekcji o parach — porównywanie par i para (wartość, numer).
Po co osobna lekcja, skoro sort(v.begin(), v.end()) już znasz? Bo ta jedna linijka to dopiero początek. Wyobraź sobie listę 30 wyników ze sprawdzianu. Kto był trzeci? Jaki wynik jest środkowy? Czy dwie osoby mają tyle samo punktów? Które dwa wyniki są najbliżej siebie? Na nieułożonej liście każde z tych pytań wymaga osobnej pętli, a czasem pętli w pętli. Na ułożonej odpowiedź po prostu leży na właściwym miejscu. Dlatego sortowanie to najczęstszy pierwszy krok w rozwiązaniach zadań olimpijskich: najpierw ułóż, potem myśl.
Uczymy się tak samo jak poprzednio. Przepisuj przykłady do swojego edytora i uruchamiaj je. Przy pytaniach „Co wypisze program?” najpierw narysuj sobie vector na kartce — rząd pudełek z numerami pod spodem — i odpowiedz w głowie, a dopiero potem sprawdzaj. W części 4 możesz też oglądać algorytmy w animacjach, krok po kroku. 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.
sort i co z niego wynika
Rosnąco i malejąco, liczby, napisy i litery, k-ty element i mediana, a potem równe obok siebie, unique i najbliżsi sąsiedzi.
Pod maską
Sortowanie przez wybieranie, bąbelkowe, przez wstawianie i przez zliczanie — sam je napiszesz i obejrzysz w animacjach.
Sortowanie po swojemu
Własna reguła porównania (lambda), kilka kryteriów naraz, stable_sort, sortowanie numerów i miejsca w rankingu.
Sortowanie w akcji
Szukanie przez połowienie, lower_bound i upper_bound, a na koniec pomysły zachłanne: posortuj i bierz po kolei.
cout << x << " " jest w porządku. Uważaj natomiast na spacje w środku wiersza i na to, czy każdy element ma być w osobnym wierszu, czy wszystkie w jednym.
Mapa lekcji
sort — wszystko po kolei jedną linijką
Zaczynamy spokojnie, od tego, co już trochę znasz. W tej części dokładnie zobaczysz, co znaczy „posortować”, jak sortować vector, zwykłą tablicę i napis, w jakiej kolejności ustawiają się słowa (to potrafi zaskoczyć!), jak posortować tylko kawałek i jak sprawdzić, czy coś już jest posortowane.
Co to znaczy „posortować”?
Posortować to ustawić elementy po kolei: od najmniejszego do największego. Robisz to codziennie, nawet o tym nie myśląc — gdy ustawiasz się w szeregu według wzrostu, gdy układasz karty w ręce albo gdy szukasz swojego nazwiska na liście, która jest ułożona alfabetycznie. Komputer robi to samo, tylko z liczbami, literami i napisami.
A co, jeśli niektóre liczby się powtarzają? Wtedy równe liczby stają obok siebie: z liczb 5, 2, 8, 2, 5 robi się 2, 2, 5, 5, 8. Taki ciąg nie jest ściśle rosnący (2 i 2 są równe), więc matematycy mówią na niego niemalejący — każdy następny element jest większy albo równy poprzedniemu. W treściach zadań zwykle pisze się po prostu „posortuj rosnąco”, a chodzi właśnie o to: równe obok siebie, w dowolnej kolejności między sobą.
sort robi dokładnie to.
sort na vectorze — pierwszy pełny program
Polecenie sort dostaje dwie strzałki z lekcji o vectorze: v.begin() — strzałkę na pierwszy element, i v.end() — strzałkę za ostatnim. Sortuje wszystko od pierwszej strzałki (wliczamy) do drugiej (nie wliczamy), czyli cały vector. Mieszka w bibliotece <algorithm>, ale <bits/stdc++.h> ma ją w środku, więc nic nie dopisujesz.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) cin >> x; // 1. wczytaj
sort(v.begin(), v.end()); // 2. posortuj
for (auto x : v) cout << x << " "; // 3. wypisz
cout << "\n";
return 0;
}
Każdy program z sortowaniem ma te same trzy kroki: wczytaj, posortuj, wypisz (albo policz coś na posortowanych danych).
Zwróć uwagę: sort nie wypisuje niczego i nie tworzy nowego vectora. Przestawia elementy w środku tego samego vectora v. Po tej linijce v jest po prostu ułożony.
Liczby ujemne nie są problemem: −3 jest mniejsze od 1, więc stoi na początku. Dwie jedynki stanęły obok siebie.
sort na zwykłej tablicy: t i t + n
Zwykła tablica nie ma begin() ani end(), ale ma coś równie dobrego: sama nazwa tablicy t działa jak strzałka na element t[0], a t + n — jak strzałka na miejsce numer n, czyli tuż za ostatnim z n elementów. Dlatego piszesz sort(t, t + n) — dokładnie jak w lekcji o parach.
int t[5] = {4, 8, 1, 9, 2};
sort(t, t + 5);
for (int i = 0; i < 5; i++) cout << t[i] << " ";
cout << "\n";
int u[6] = {0, 7, 3, 6, 5, 1}; // liczymy od 1: u[1]..u[5]
int n = 5;
sort(u + 1, u + n + 1);
for (int i = 1; i <= n; i++) cout << u[i] << " ";
cout << "\n";
Drugi przykład to częsty zwyczaj na olimpiadzie: elementy trzyma się w pudełkach od 1 do n, a pudełko 0 zostaje puste. Wtedy sortujesz od u + 1 (pudełko 1) do u + n + 1 (miejsce za pudełkiem n).
Najważniejsza zasada jest ta sama co przy vectorze: druga strzałka pokazuje miejsce, którego już nie bierzemy.
sort(t, t + n - 1). Wygląda logicznie („ostatni element ma numer n − 1”), ale druga strzałka nie jest wliczana — więc ostatni element zostaje poza sortowaniem i stoi tam, gdzie stał. Program działa „prawie” dobrze, co jest najgorszym rodzajem błędu. Zapamiętaj: sort(t, t + n) dla pudełek 0..n−1 i sort(t + 1, t + n + 1) dla pudełek 1..n.
Słowa po kolei: porządek słownikowy
Vector napisów sortuje się tak samo: sort(s.begin(), s.end()). Słowa ustawią się w porządku słownikowym — tak jak w słowniku albo w dzienniku. Pamiętasz z lekcji o napisach, jak C++ porównuje dwa napisy? Idzie od lewej, litera po literze, i rozstrzyga na pierwszej różnicy. Gdy jedno słowo jest początkiem drugiego, krótsze stoi wcześniej. Zobacz, co z tego wynika:
vector<string> s = {"kotek", "ala", "kot", "Zosia", "ania", "10", "9"};
sort(s.begin(), s.end());
for (auto x : s) cout << x << "\n";
| para | pierwsza różnica | kto wcześniej |
|---|---|---|
"ala" i "ania" | 'l' i 'n' | ala — l jest przed n |
"kot" i "kotek" | kot się skończył | kot — krótszy, gdy jest początkiem |
"Zosia" i "ala" | 'Z' (kod 90) i 'a' (kod 97) | Zosia — wielkie litery są przed małymi |
"10" i "9" | '1' i '9' | 10 — bo znak '1' jest przed '9' |
Dwie rzeczy zaskakują prawie każdego. Po pierwsze, wszystkie wielkie litery są przed wszystkimi małymi: „Zosia” stoi przed „ala”, bo komputer porównuje kody znaków, a kody wielkich liter (65–90) są mniejsze od kodów małych (97–122). Cyfry mają kody jeszcze mniejsze (48–57), więc stoją przed literami. Po drugie, liczby zapisane jako napisy sortują się jak słowa: „10” stoi przed „9”, bo porównujemy pierwsze znaki '1' i '9'. Liczba 10 jest większa od 9, ale napis „10” jest „mniejszy” od napisu „9”.
int albo long long. Napis „100” stanie przed „20”, a „-5” przed „-10”, bo napisy porównują się znak po znaku, a nie według wartości.
Litery w napisie
Napis to w środku rząd znaków — prawie jak vector. Dlatego sort(s.begin(), s.end()) ustawia po kolei litery jednego napisu. Znaki porównują się po kodach, więc spacje (kod 32) idą na sam początek, potem cyfry, wielkie litery i na końcu małe.
string s = "banan";
sort(s.begin(), s.end());
cout << s << "\n";
string t = "Ala ma kota";
sort(t.begin(), t.end());
cout << "[" << t << "]\n";
W drugim przykładzie dwie spacje wylądowały na początku, potem wielkie A, potem cztery małe a i reszta liter po kolei. Nawiasy kwadratowe wypisaliśmy tylko po to, żeby spacje było widać.
Sortowanie liter ma piękne zastosowanie: anagramy. Dwa słowa są anagramami, gdy składają się z tych samych liter, tylko w innej kolejności — jak „kot” i „tok”. Po posortowaniu liter oba zamieniają się w to samo: „kot”. Wystarczy więc posortować litery obu słów i porównać wyniki przez ==.
string a = "kajak", b = "jakak", c = "kajko";
string sa = a, sb = b, sc = c; // kopie — oryginały zostają
sort(sa.begin(), sa.end());
sort(sb.begin(), sb.end());
sort(sc.begin(), sc.end());
cout << sa << " " << sb << " " << sc << "\n";
cout << a << " i " << b << ": " << (sa == sb) << "\n";
cout << a << " i " << c << ": " << (sa == sc) << "\n";
Zwróć uwagę na kopie: sortujemy sa, a nie a. Gdybyśmy posortowali samo a, stracilibyśmy oryginalne słowo i nie dałoby się go już wypisać.
Tylko kawałek
Z lekcji o vectorze pamiętasz, że strzałki nie muszą obejmować całości. Kawałek od numeru a do numeru b włącznie sortujesz tak: sort(v.begin() + a, v.begin() + b + 1). To + 1 jest potrzebne, bo druga strzałka pokazuje pudełko, którego już nie bierzemy. Reszta vectora zostaje nietknięta.
vector<int> v = {9, 7, 5, 3, 1, 8, 6};
int a = 1, b = 4;
sort(v.begin() + a, v.begin() + b + 1); // numery 1..4
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin() + 4, v.end()); // od numeru 4 do końca
for (auto x : v) cout << x << " ";
cout << "\n";
sort zmienia vector — czasem potrzebna kopia
Po sort pierwotna kolejność jest stracona — vector nie pamięta, jak wyglądał wcześniej. Czasem to nie szkodzi (gdy pytają tylko o ułożone liczby), ale czasem potrzebujesz obu wersji: na przykład, żeby porównać, które elementy stały już na swoich miejscach. Wtedy robisz kopię: vector<int> w = v; i sortujesz kopię.
vector<int> v = {3, 1, 2, 4, 5};
vector<int> w = v; // kopia
sort(w.begin(), w.end());
int naMiejscu = 0;
for (int i = 0; i < (int)v.size(); i++) {
if (v[i] == w[i]) naMiejscu++;
}
cout << naMiejscu << "\n";
Czy to już jest posortowane?
Ciąg jest posortowany niemalejąco wtedy, gdy każde dwa sąsiednie elementy stoją dobrze: v[i] <= v[i + 1]. Wystarczy więc przejść po sąsiadach i poszukać pary, w której lewy jest większy od prawego. Jeśli takiej pary nie ma — ciąg jest posortowany. To samo robi gotowe polecenie is_sorted(v.begin(), v.end()), które zwraca true albo false.
vector<int> v = {1, 3, 3, 8, 6, 9};
int zle = -1; // numer pierwszej złej pary
for (int i = 0; i + 1 < (int)v.size(); i++) {
if (v[i] > v[i + 1]) {
zle = i;
break;
}
}
if (zle == -1) cout << "posortowane\n";
else cout << "zle przy numerze " << zle << ": " << v[zle] << " > " << v[zle + 1] << "\n";
cout << is_sorted(v.begin(), v.end()) << "\n";
Warunek pętli to i + 1 < v.size(), bo porównujemy v[i] z v[i + 1] — ostatnie i musi mieć jeszcze sąsiada po prawej.
Uwaga na znak: posortowane niemalejąco to v[i] <= v[i + 1], więc „źle” to v[i] > v[i + 1]. Dwa równe elementy obok siebie są w porządku.
is_sorted wypisane przez cout daje 1 (tak) albo 0 (nie) — jak każdy bool.
Inne typy działają tak samo
sort potrafi ustawić po kolei wszystko, co da się porównać znakiem <: liczby long long i double, znaki char, napisy, a nawet pary — te porównują się najpierw po first, a przy remisie po second, jak w lekcji o parach. Wrócimy do nich w części 6.
vector<double> d = {3.5, -1.25, 2, 0.5};
sort(d.begin(), d.end());
for (auto x : d) cout << x << " ";
cout << "\n";
vector<char> z = {'k', 'C', '7', 'a'};
sort(z.begin(), z.end());
for (auto x : z) cout << x << " ";
cout << "\n";
vector<pair<int, int>> p = {{2, 5}, {1, 9}, {2, 1}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << a << "," << b << " ";
cout << "\n";
Znaki: cyfra '7' (kod 55) przed wielkim 'C' (67), a ono przed małymi 'a' (97) i 'k' (107).
Pary: (1, 9) jest pierwsza, bo ma najmniejsze first. Pary (2, 5) i (2, 1) remisują na first, więc rozstrzyga second: 1 < 5.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {5, 3, 8, 3};
sort(v.begin(), v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
string s = "Kot";
sort(s.begin(), s.end());
cout << s;
Pokaż odpowiedź
K (kod 75) jest przed małymi o (111) i t (116), a o przed t — litery już stały po kolei.vector<string> s = {"b", "B", "a"};
sort(s.begin(), s.end());
for (auto x : s) cout << x;
Pokaż odpowiedź
B jest przed wszystkimi małymi literami.int t[5] = {5, 4, 3, 2, 1};
sort(t, t + 3);
for (int i = 0; i < 5; i++) cout << t[i];
Pokaż odpowiedź
vector<int> v = {9, 1, 8, 2, 7};
sort(v.begin() + 1, v.end());
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<string> s = {"3", "100", "20"};
sort(s.begin(), s.end());
for (auto x : s) cout << x << " ";
Pokaż odpowiedź
vector<int> v = {1, 2, 2, 3};
cout << is_sorted(v.begin(), v.end());
Pokaż odpowiedź
string a = "lato", b = "tola";
sort(a.begin(), a.end());
sort(b.begin(), b.end());
cout << a << " " << (a == b);
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ę.
Malejąco, k-ty element i mediana
W rankingach zwykle chcemy odwrotnie: najlepszy wynik na górze. W tej części poznasz trzy sposoby sortowania malejąco i zobaczysz, że w posortowanym vectorze każde pytanie w stylu „kto jest k-ty?” albo „jaki wynik jest środkowy?” ma odpowiedź pod konkretnym numerem pudełka.
Sposób 1: sort, a potem reverse
Ten sposób znasz z lekcji o vectorze: najpierw ustawiasz rosnąco, a potem odwracasz kolejność poleceniem reverse. Najmniejszy element ląduje na końcu, największy — na początku.
vector<int> v = {4, 9, 1, 7, 3};
sort(v.begin(), v.end()); // 1 3 4 7 9
reverse(v.begin(), v.end()); // 9 7 4 3 1
for (auto x : v) cout << x << " ";
cout << "\n";
Sposób 2: strzałki od tyłu — rbegin() i rend()
Vector ma też strzałki, które chodzą od tyłu. Literka r w nazwie znaczy reverse — odwrotnie. v.rbegin() pokazuje ostatni element i przesuwa się w lewo, a v.rend() stoi tuż przed pierwszym — to „koniec” dla kogoś, kto idzie od prawej do lewej.
Co się stanie, gdy dasz sort strzałki od tyłu? sort ustawi elementy rosnąco w kolejności, w jakiej je widzi, czyli od prawej do lewej. Jeśli patrząc od prawej liczby rosną, to patrząc normalnie, od lewej — maleją. Jedna linijka i gotowe: sort(v.rbegin(), v.rend()).
vector<int> v = {4, 9, 1, 7, 3};
sort(v.rbegin(), v.rend());
for (auto x : v) cout << x << " ";
cout << "\n";
string s = "banan";
sort(s.rbegin(), s.rend());
cout << s << "\n";
Działa też dla napisów: litery ustawiają się od końca alfabetu.
Ta sztuczka wygląda tajemniczo, ale w praktyce to po prostu „przepis na malejąco”. Nie musisz za każdym razem analizować, dlaczego działa.
Sposób 3: gotowa reguła greater
sort może dostać trzeci argument: regułę, która mówi, który z dwóch elementów ma stać wcześniej. Domyślna reguła to „mniejszy przed większym”. C++ ma gotową regułę odwrotną: greater<int>() — „większy przed mniejszym”. W nawiasach ostrych piszesz typ elementów vectora. O własnych regułach będzie cała część 5.
vector<int> v = {4, 9, 1, 7, 3};
sort(v.begin(), v.end(), greater<int>());
for (auto x : v) cout << x << " ";
cout << "\n";
vector<string> s = {"ola", "ewa", "zosia", "ala"};
sort(s.begin(), s.end(), greater<string>());
for (auto x : s) cout << x << " ";
cout << "\n";
Wszystkie trzy sposoby dają ten sam wynik. Wybierz jeden i się go trzymaj. sort(v.rbegin(), v.rend()) jest najkrótszy, greater<int>() najłatwiej przeczytać, a sort + reverse najłatwiej zapamiętać.
Uwaga na typ: dla vector<long long> piszesz greater<long long>(), dla napisów greater<string>(). Nawiasy () na końcu są obowiązkowe.
W posortowanym każdy ma swój adres
Po posortowaniu rosnąco odpowiedzi na wiele pytań po prostu leżą pod znanymi numerami. Zakładamy, że v ma n elementów, numerowanych od 0:
| pytanie | po sort rosnąco | dla 3 5 5 8 10 12 (n = 6) |
|---|---|---|
| najmniejszy | v[0] | 3 |
| największy | v[n - 1] | 12 |
| k-ty najmniejszy (k od 1) | v[k - 1] | k = 2: 5 |
| k-ty największy | v[n - k] | k = 2: 10 |
| k najmniejszych | v[0] … v[k - 1] | k = 3: 3 5 5 |
| k największych | v[n - k] … v[n - 1] | k = 3: 8 10 12 |
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> v(n);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
cout << "najmniejszy: " << v[0] << "\n";
cout << "najwiekszy: " << v[n - 1] << "\n";
cout << k << ". od dolu: " << v[k - 1] << "\n";
cout << k << ". od gory: " << v[n - k] << "\n";
return 0;
}
Po sortowaniu: 40 58 66 72 85 85 91. Trzeci od dołu to v[2] = 66. Trzeci od góry to v[7 − 3] = v[4] = 85 — ten sam wynik co drugi od góry, bo dwie osoby mają po 85.
Wzór v[n - k] łatwo sprawdzić dla k = 1: v[n - 1], czyli ostatni — największy. Zgadza się.
Mediana — wartość środkowa
Mediana to liczba, która po posortowaniu stoi w samym środku: połowa liczb jest od niej mniejsza (albo równa), połowa — większa (albo równa). Dlaczego nie średnia? Bo średnią potrafi zepsuć jedna dziwna liczba. Pięć osób zarabia 2000, 2100, 2300, 2500 i 50 000 zł. Średnia to 11 780 zł — nikt tyle nie zarabia! Mediana to 2300 zł i ona naprawdę mówi, ile zarabia „typowa” osoba.
Gdy n jest nieparzyste, środek jest jeden: v[n / 2] (dzielenie całkowite). Dla n = 5 to v[2] — przed nim stoją dwa elementy i za nim dwa. Gdy n jest parzyste, środki są dwa: v[n / 2 - 1] i v[n / 2]. Wtedy medianą zwykle nazywa się ich średnią — ale zawsze czytaj, co dokładnie mówi zadanie.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
cout << fixed << setprecision(1);
if (n % 2 == 1) {
cout << (double)v[n / 2] << "\n";
} else {
cout << (v[n / 2 - 1] + v[n / 2]) / 2.0 << "\n";
}
return 0;
}
Dzielimy przez 2.0, a nie przez 2. Pamiętasz pułapkę z pierwszej lekcji? (3 + 4) / 2 to 3, bo dzielenie dwóch liczb całkowitych obcina część po przecinku. (3 + 4) / 2.0 to 3.5.
W gałęzi z nieparzystym n zamieniamy liczbę na double, żeby obie odpowiedzi wyglądały tak samo — z jedną cyfrą po kropce.
Uwaga na ogromne liczby: suma dwóch liczb rzędu 2 miliardów nie mieści się w int. W zadaniach z dużymi wartościami trzymaj je w long long.
Najlepsze k: suma i próg
Po posortowaniu k największych liczb stoi na końcu, w pudełkach od n − k do n − 1. Suma k najlepszych wyników to po prostu suma tego kawałka. A teraz pytanie podchwytliwe: do finału przechodzi k najlepszych zawodników, ale remisy na granicy też przechodzą. Ile osób awansuje? Próg to wynik k-tego najlepszego, czyli v[n - k], a awansują wszyscy z wynikiem co najmniej takim jak próg — może ich być więcej niż k.
vector<int> v = {70, 85, 90, 85, 60, 85, 95};
int n = v.size(), k = 3;
sort(v.begin(), v.end()); // 60 70 85 85 85 90 95
long long suma = 0;
for (int i = n - k; i < n; i++) suma += v[i];
int prog = v[n - k];
int ile = 0;
for (auto x : v) {
if (x >= prog) ile++;
}
cout << "suma " << k << " najlepszych: " << suma << "\n";
cout << "prog: " << prog << ", awansuje: " << ile << "\n";
Cyfry liczby: największa i najmniejsza
Ciekawe zadanie: z cyfr liczby 30 521 ułóż największą i najmniejszą możliwą liczbę. Wczytujemy liczbę jako napis — wtedy każda cyfra to osobny znak i możemy je sortować. Największa liczba to cyfry malejąco: 53 210. Najmniejsza to cyfry rosnąco: 01 235… ale liczba nie może zaczynać się od zera! Rozwiązanie: po posortowaniu rosnąco znajdź pierwszą cyfrę różną od zera i zamień ją z cyfrą na początku. Z 01 235 robi się 10 235.
string s = "30521";
string duza = s, mala = s;
sort(duza.rbegin(), duza.rend()); // 53210
sort(mala.begin(), mala.end()); // 01235
int i = 0;
while (i < (int)mala.size() && mala[i] == '0') i++;
if (i < (int)mala.size()) swap(mala[0], mala[i]);
cout << duza << " " << mala << "\n";
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {4, 1, 3};
sort(v.rbegin(), v.rend());
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {2, 9, 2, 5};
sort(v.begin(), v.end(), greater<int>());
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {7, 2, 9, 4, 1};
sort(v.begin(), v.end());
cout << v[1] << " " << v[v.size() - 2];
Pokaż odpowiedź
v[1] to drugi najmniejszy (2), a v[n - 2] to drugi największy (7).vector<int> v = {5, 1, 4, 2, 3};
sort(v.begin(), v.end());
cout << v[v.size() / 2];
Pokaż odpowiedź
v[2] w ciągu 1 2 3 4 5.vector<int> v = {4, 1, 3, 2};
sort(v.begin(), v.end());
cout << (v[1] + v[2]) / 2;
Pokaż odpowiedź
5 / 2 w liczbach całkowitych daje 2. Żeby dostać 2.5, dziel przez 2.0.string s = "2024";
sort(s.rbegin(), s.rend());
cout << s;
Pokaż odpowiedź
vector<int> v = {10, 30, 20, 30};
sort(v.begin(), v.end());
cout << v[v.size() - 2];
Pokaż odpowiedź
v[2] = 30 — taki sam jak pierwszy, bo trzydziestki są dwie.vector<int> v = {5, 1, 5, 3};
sort(v.begin(), v.end());
int s = 0;
for (int i = 2; i < 4; i++) s += v[i];
cout << s;
Pokaż odpowiedź
9 ć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ę.
Po sortowaniu: równe obok siebie, najbliżsi obok siebie
Sortowanie robi z danymi dwie bardzo pożyteczne rzeczy. Po pierwsze: równe wartości stają obok siebie, więc łatwo je policzyć i pogrupować. Po drugie: liczby bliskie sobie też stają obok siebie, więc najmniejszą różnicę znajdziesz, patrząc tylko na sąsiadów. W tej części wykorzystasz obie te rzeczy.
Równe liczby tworzą grupy
Spójrz na liczby 5, 2, 8, 2, 5, 5. W nieposortowanym ciągu piątki są porozrzucane i żeby je policzyć, trzeba przejrzeć wszystko. Po posortowaniu wszystkie piątki tworzą jeden kawałek bez przerw — będziemy go nazywać grupą.
Ile jest różnych liczb?
W posortowanym ciągu nowa wartość zaczyna się dokładnie tam, gdzie v[i] != v[i - 1] — element różni się od swojego lewego sąsiada. Pierwszy element zawsze zaczyna grupę. Liczba różnych wartości to więc 1 plus liczba miejsc, w których coś się zmienia.
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end()); // 2 2 5 5 5 8
int roznych = 1;
for (int i = 1; i < (int)v.size(); i++) {
if (v[i] != v[i - 1]) roznych++;
}
cout << roznych << "\n";
| i | v[i − 1] | v[i] | różne? | roznych |
|---|---|---|---|---|
| start | — | — | — | 1 |
| 1 | 2 | 2 | nie | 1 |
| 2 | 2 | 5 | tak | 2 |
| 3 | 5 | 5 | nie | 2 |
| 4 | 5 | 5 | nie | 2 |
| 5 | 5 | 8 | tak | 3 |
sort, potem liczenie. Ten sam kod nie zadziała też dla pustego vectora (zaczynamy od 1) — w zadaniach n jest zwykle co najmniej 1, ale warto o tym pamiętać.
Grupa po grupie: wartość i ile razy
Teraz chcemy wypisać każdą wartość razem z liczbą jej wystąpień. Użyjemy schematu z dwoma numerami: i to początek grupy, a j biegnie w prawo, dopóki widzi tę samą wartość. Gdy j się zatrzyma, grupa to pudełka od i do j − 1, ma j − i elementów, a następna grupa zaczyna się w j — więc i przeskakuje na j.
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end());
int n = v.size();
int i = 0;
while (i < n) {
int j = i;
while (j < n && v[j] == v[i]) j++;
cout << v[i] << " x" << j - i << "\n";
i = j; // skok na początek następnej grupy
}
Ten schemat warto zapamiętać — przyda się w wielu zadaniach. Zauważ warunek j < n && v[j] == v[i]: najpierw sprawdzamy, czy j nie wyszło za vector, a dopiero potem czytamy v[j]. Odwrotna kolejność czytałaby pudełko spoza vectora.
Pewnie pamiętasz z lekcji o tablicach tablicę liczników, która robi podobną rzecz. Działa jednak tylko dla małych liczb — dla liczby 1 000 000 000 potrzebowałbyś miliarda liczników! Sortowanie i grupy działają dla dowolnych wartości: ogromnych, ujemnych, a nawet napisów.
Najczęstsza wartość
Najczęstsza wartość to ta z najdłuższą grupą. Przechodzimy grupa po grupie i zapamiętujemy najlepszą. Jeśli kilka wartości remisuje, zwykle zadanie każe wybrać najmniejszą — a ponieważ grupy idą od najmniejszych wartości, wystarczy zmieniać zapamiętaną wartość tylko przy ściśle dłuższej grupie (znak >, nie >=).
vector<int> v = {4, 7, 4, 1, 7, 9, 7, 4};
sort(v.begin(), v.end()); // 1 4 4 4 7 7 7 9
int n = v.size();
int najW = v[0], najIle = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && v[j] == v[i]) j++;
if (j - i > najIle) { // ściśle więcej
najIle = j - i;
najW = v[i];
}
i = j;
}
cout << najW << " (" << najIle << " razy)\n";
Czwórki i siódemki występują po 3 razy. Najpierw trafiamy na grupę czwórek (3 > 0, zapamiętujemy). Grupa siódemek też ma 3, ale 3 nie jest większe od 3 — zostaje czwórka, czyli mniejsza z remisujących wartości.
Gdybyś napisał >=, wygrałaby siódemka — ostatnia z remisujących.
unique — powtórzenia znikają jedną linijką
Często chcesz zostawić tylko różne wartości. Służy do tego zestaw dwóch poleceń, który pisze się zawsze razem:
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
Jak to działa? unique przechodzi po vectorze i z każdej grupy stojących obok siebie równych elementów zostawia jeden, przesuwając je na początek. Vectora jednak nie skraca: na końcu zostają jakieś śmieci, a unique zwraca strzałkę na miejsce, w którym się zaczynają — nowy koniec. Dlatego od razu wołamy erase, który usuwa wszystko od tej strzałki do end().
vector<int> v = {5, 2, 8, 2, 5, 5};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size() << ":";
for (auto x : v) cout << " " << x;
cout << "\n";
vector<int> v = {5, 2, 5, 5, 2};
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size() << ":";
for (auto x : v) cout << " " << x;
cout << "\n";
unique zbija tylko powtórzenia, które stoją obok siebie. W przykładzie po prawej sklejone zostały tylko dwie piątki ze środka — reszta została. Zawsze: najpierw sort, potem unique, a unique zawsze razem z erase.
Najbliżsi sąsiedzi
Przy prostej drodze stoją domy. Które dwa stoją najbliżej siebie? Naiwnie: sprawdź każdą parę domów — przy 100 000 domów to 5 miliardów par, o wiele za dużo. Sprytnie: posortuj pozycje. Dwa najbliższe domy na pewno staną wtedy obok siebie — wystarczy porównać tylko sąsiadów: v[i + 1] - v[i].
Dlaczego? Weźmy trzy domy a ≤ b ≤ c. Odległość od a do c to (b − a) + (c − b) — jest co najmniej tak duża jak każda z dwóch krótszych. Dom, który stoi „pomiędzy”, zawsze jest bliżej. Dlatego para nie-sąsiadów nigdy nie wygra z parą sąsiadów.
vector<int> v = {40, 7, 22, 31, 12, 60};
sort(v.begin(), v.end()); // 7 12 22 31 40 60
int najmniej = v[1] - v[0];
int najwiecej = v[1] - v[0];
for (int i = 0; i + 1 < (int)v.size(); i++) {
int d = v[i + 1] - v[i];
najmniej = min(najmniej, d);
najwiecej = max(najwiecej, d);
}
cout << "najblizej: " << najmniej << "\n";
cout << "najwieksza przerwa: " << najwiecej << "\n";
Okno k elementów: najmniejszy rozrzut
Trener chce wybrać do sztafety k zawodników o jak najbardziej podobnym czasie — tak, żeby różnica między najszybszym a najwolniejszym z nich była jak najmniejsza. Po posortowaniu najlepiej wybrać k zawodników stojących kolejno obok siebie. Każde takie „okno” od numeru i do i + k − 1 ma rozrzut v[i + k - 1] - v[i] (ostatni minus pierwszy), i spośród okien wybieramy najlepsze.
vector<int> v = {50, 41, 63, 47, 58, 44};
int k = 3;
sort(v.begin(), v.end()); // 41 44 47 50 58 63
int najlepiej = v[k - 1] - v[0];
for (int i = 0; i + k - 1 < (int)v.size(); i++) {
najlepiej = min(najlepiej, v[i + k - 1] - v[i]);
}
cout << najlepiej << "\n";
Dlaczego wybór „z dziurami” nie może być lepszy? Jeśli wybierzesz k zawodników i między najszybszym a najwolniejszym z nich stoi ktoś niewybrany, możesz wymienić na niego jednego ze skrajnych — rozrzut nie wzrośnie. Wymieniając tak dalej, dojdziesz do okna bez dziur, które jest co najmniej tak dobre.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {3, 1, 3, 2, 1};
sort(v.begin(), v.end());
int r = 1;
for (int i = 1; i < 5; i++) if (v[i] != v[i - 1]) r++;
cout << r;
Pokaż odpowiedź
vector<int> v = {3, 1, 3, 1, 3};
sort(v.begin(), v.end());
int i = 0;
while (i < 5) {
int j = i;
while (j < 5 && v[j] == v[i]) j++;
cout << v[i] << ":" << j - i << " ";
i = j;
}
Pokaż odpowiedź
vector<int> v = {1, 1, 2, 1};
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size();
Pokaż odpowiedź
unique skleja tylko dwie jedynki z początku: zostaje 1 2 1.vector<int> v = {1, 1, 2, 1};
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
cout << v.size();
Pokaż odpowiedź
vector<int> v = {10, 4, 7, 15};
sort(v.begin(), v.end());
int m = 1000;
for (int i = 0; i + 1 < 4; i++) m = min(m, v[i + 1] - v[i]);
cout << m;
Pokaż odpowiedź
vector<int> v = {1, 5, 6, 10};
int k = 2, b = 1000;
for (int i = 0; i + k - 1 < 4; i++) b = min(b, v[i + k - 1] - v[i]);
cout << b;
Pokaż odpowiedź
vector<int> v = {4, 2, 4, 2, 7};
sort(v.begin(), v.end());
int w = v[0], best = 0, i = 0;
while (i < 5) {
int j = i;
while (j < 5 && v[j] == v[i]) j++;
if (j - i > best) { best = j - i; w = v[i]; }
i = j;
}
cout << w << " " << best;
Pokaż odpowiedź
>.vector<string> s = {"kot", "pies", "kot", "mysz", "pies", "kot"};
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
for (auto x : s) cout << x << " ";
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ę.
Jak sortuje komputer? Sortowanie ręcznie
sort to gotowe narzędzie i w zadaniach będziesz go używać prawie zawsze. Mimo to warto raz zobaczyć, jak można sortować samemu. Po pierwsze — to świetny trening pętli, ifów i swap. Po drugie — zadania czasem pytają o przebieg konkretnego algorytmu: „ile zamian zrobi sortowanie bąbelkowe?”. Po trzecie — zrozumiesz, dlaczego jedne sposoby są szybkie, a inne wolne.
Poznasz cztery metody. Przy każdej jest animacja: klikaj „Krok ▸”, żeby oglądać algorytm ruch po ruchu, albo „Odtwórz”, żeby leciał sam. Pod słupkami jest opis tego, co dzieje się w danym kroku, i numery pudełek. „Nowe liczby” losuje inne dane — sprawdź, czy przewidzisz następny ruch!
Sortowanie przez wybieranie
Pomysł jest taki, jak przy ustawianiu szeregu na WF-ie. Wybierz najniższą osobę i postaw ją na pierwszym miejscu. Z pozostałych wybierz najniższą i postaw na drugim. I tak dalej. Po angielsku: selection sort.
W programie: w rundzie numer i szukamy najmniejszego elementu w kawałku od i do końca (zapamiętujemy jego numer m) i zamieniamy go z elementem v[i]. Po tej rundzie pudełko i jest gotowe i już go nie ruszamy.
vector<int> v = {5, 2, 4, 1, 3};
int n = v.size();
for (int i = 0; i < n - 1; i++) {
int m = i; // numer najmniejszego od i do końca
for (int j = i + 1; j < n; j++) {
if (v[j] < v[m]) m = j;
}
swap(v[i], v[m]); // najmniejszy na miejsce i
for (auto x : v) cout << x << " ";
cout << "\n";
}
| runda i | szukamy w | najmniejszy | po zamianie |
|---|---|---|---|
| 0 | 5 2 4 1 3 | 1 (m = 3) | 1 2 4 5 3 |
| 1 | 2 4 5 3 | 2 (m = 1) | 1 2 4 5 3 |
| 2 | 4 5 3 | 3 (m = 4) | 1 2 3 5 4 |
| 3 | 5 4 | 4 (m = 4) | 1 2 3 4 5 |
W rundzie 1 najmniejszy już stał na swoim miejscu (m = i), więc swap zamienia element sam ze sobą — nic się nie dzieje i ciąg się nie zmienia. Ostatniej rundy (i = n − 1) nie ma, bo jeden element, który został, sam stoi na właściwym miejscu.
Ile porównań v[j] < v[m] wykona ta metoda? W pierwszej rundzie n − 1, w drugiej n − 2, … w ostatniej 1. Razem (n − 1) + (n − 2) + … + 1 = n·(n − 1) / 2. Dla n = 5 to 10, dla n = 1000 to prawie pół miliona, dla n = 100 000 — prawie 5 miliardów. Zapamiętaj tę liczbę, wrócimy do niej.
Sortowanie bąbelkowe
Tu porównujemy tylko sąsiadów. Idziemy od lewej do prawej i gdy dwaj sąsiedzi stoją w złej kolejności (lewy większy od prawego), zamieniamy ich miejscami. Po jednym takim przejściu — rundzie — największy element na pewno „wypłynie” na sam koniec, jak bąbelek powietrza w wodzie. Stąd nazwa: bubble sort. W następnej rundzie na przedostatnie miejsce wypłynie drugi największy, i tak dalej.
vector<int> v = {5, 1, 4, 2, 8};
int n = v.size();
int zamian = 0;
for (int runda = 0; runda < n - 1; runda++) {
bool bylaZamiana = false;
for (int j = 0; j + 1 < n - runda; j++) {
if (v[j] > v[j + 1]) {
swap(v[j], v[j + 1]);
zamian++;
bylaZamiana = true;
}
}
cout << "po rundzie " << runda + 1 << ":";
for (auto x : v) cout << " " << x;
cout << "\n";
if (!bylaZamiana) break; // nic się nie zmieniło — koniec
}
cout << "zamian: " << zamian << "\n";
Runda 1: 5 i 1 — zamiana; 5 i 4 — zamiana; 5 i 2 — zamiana; 5 i 8 — dobrze. Piątka przepłynęła trzy miejsca w prawo, a ósemka stoi na końcu.
Runda 2: zamienia się tylko para 4 i 2. Runda 3: nic się nie zamienia — wszystko już stoi po kolei, więc break kończy pętlę. Bez tej flagi bylaZamiana program niepotrzebnie wykonałby jeszcze rundę 4.
Warunek j + 1 < n - runda: w każdej kolejnej rundzie pomijamy końcówkę, bo tam stoją już największe, gotowe elementy.
Sortowanie przez wstawianie
Tak układasz karty w ręce: lewa część ręki jest już ułożona, bierzesz kolejną kartę i wsuwasz ją w odpowiednie miejsce, przesuwając większe karty w prawo. Po angielsku: insertion sort.
W programie: dla każdego i od 1 do n − 1 zapamiętujemy x = v[i]. Potem idziemy w lewo od j = i − 1 i dopóki v[j] > x, przesuwamy v[j] o jedno pudełko w prawo. Gdy natrafimy na element nie większy od x (albo dojdziemy do początku), x wskakuje w zwolnione miejsce j + 1.
vector<int> v = {7, 3, 5, 1, 6};
int n = v.size();
for (int i = 1; i < n; i++) {
int x = v[i]; // karta, którą wstawiamy
int j = i - 1;
while (j >= 0 && v[j] > x) {
v[j + 1] = v[j]; // większa karta w prawo
j--;
}
v[j + 1] = x; // x w wolne miejsce
for (auto y : v) cout << y << " ";
cout << "\n";
}
Warunek j >= 0 && v[j] > x — najpierw pilnujemy, żeby j nie wyszło przed vector, a dopiero potem czytamy v[j].
Ciekawostka: wstawianie jest bardzo szybkie, gdy dane są prawie posortowane — każda karta przesuwa się wtedy tylko o kilka miejsc. Gdy dane są ułożone odwrotnie, każda nowa karta wędruje aż na początek i porównań jest znowu około n·n / 2.
Sortowanie przez zliczanie
Tę metodę znasz z lekcji o tablicach, choć może nie wiedziałeś, że to sortowanie. Gdy wartości są małe — oceny 1–6, wiek 0–120, cyfry 0–9 — w ogóle nie trzeba ich porównywać. Robimy licznik dla każdej możliwej wartości, przechodzimy po danych i zwiększamy liczniki. Potem idziemy po licznikach od najmniejszej wartości i każdą wartość wypisujemy tyle razy, ile mówi jej licznik.
vector<int> oceny = {4, 6, 3, 4, 5, 2, 4, 6};
vector<int> licznik(7, 0); // pudełka 0..6, używamy 1..6
for (auto x : oceny) licznik[x]++;
for (int w = 1; w <= 6; w++) {
for (int k = 0; k < licznik[w]; k++) cout << w << " ";
}
cout << "\n";
for (int w = 1; w <= 6; w++) cout << w << ": " << licznik[w] << " ";
cout << "\n";
To najszybsza metoda z tej części: jedno przejście po danych i jedno po licznikach. Ma jednak wadę — działa tylko wtedy, gdy wartości są małe i nieujemne (albo da się je łatwo przesunąć, np. dodając stałą). Dla liczb do miliarda potrzebowalibyśmy miliarda liczników.
Przy okazji dostajemy za darmo liczbę wystąpień każdej oceny — to drugi wiersz wyniku.
Ile to trwa? Dwie pętle kontra sort
Wybieranie, bąbelki i wstawianie mają pętlę w pętli, więc dla n elementów wykonują rzędu n·n operacji. Gotowe sort używa sprytniejszych metod, które dzielą dane na połówki — robi rzędu n·log2n operacji (log2n to mniej więcej „ile razy da się podzielić n na pół”, dla miliona to około 20). Komputer wykonuje około 100–300 milionów prostych operacji na sekundę. Porównaj:
| n | dwie pętle: około n·n | sort: około n·log₂n |
|---|---|---|
| 10 | 100 | około 35 |
| 1 000 | 1 000 000 — błyskawicznie | około 10 000 |
| 10 000 | 100 000 000 — ok. pół sekundy | około 140 000 |
| 100 000 | 10 000 000 000 — kilkadziesiąt sekund, za wolno! | około 1 700 000 — błyskawicznie |
| 1 000 000 | 1012 — godziny | około 20 000 000 — ułamek sekundy |
sort — chyba że zadanie pyta o przebieg konkretnego algorytmu (np. ile zamian zrobią bąbelki) albo wartości są tak małe, że wygodniej zliczać. Metody z dwiema pętlami pisz po to, żeby zrozumieć sortowanie i przećwiczyć pętle — przy n do kilku tysięcy też zdążą.
Dla ciekawych: jak robi to sort?
Szybkie metody dzielą problem na mniejsze kawałki. Sortowanie przez scalanie dzieli dane na dwie połówki, sortuje każdą osobno (tak samo — dzieląc dalej), a potem scala dwie ułożone połówki w jedną: porównuje ich początki i bierze mniejszy. Sortowanie szybkie wybiera jedną liczbę — piwot — i ustawia mniejsze od niej na lewo, a większe na prawo; potem robi to samo z każdą stroną. Obie metody wymagają rekurencji — funkcji, która woła samą siebie — więc ich kod napiszesz w lekcji Rekurencja. Na razie po prostu popatrz:
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {4, 3, 1, 2};
int m = 0;
for (int j = 1; j < 4; j++) if (v[j] < v[m]) m = j;
swap(v[0], v[m]);
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {4, 3, 1, 2};
for (int j = 0; j + 1 < 4; j++)
if (v[j] > v[j + 1]) swap(v[j], v[j + 1]);
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {4, 3, 1, 2};
for (int i = 1; i < 3; i++) {
int x = v[i], j = i - 1;
while (j >= 0 && v[j] > x) { v[j + 1] = v[j]; j--; }
v[j + 1] = x;
}
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {3, 2, 1};
int z = 0;
for (int r = 0; r < 2; r++)
for (int j = 0; j + 1 < 3 - r; j++)
if (v[j] > v[j + 1]) { swap(v[j], v[j + 1]); z++; }
cout << z;
Pokaż odpowiedź
int n = 5, p = 0;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++) p++;
cout << p;
Pokaż odpowiedź
vector<int> v = {3, 1, 3, 0};
vector<int> c(4, 0);
for (auto x : v) c[x]++;
for (int w = 0; w < 4; w++)
for (int k = 0; k < c[w]; k++) cout << w;
Pokaż odpowiedź
vector<int> v = {1, 2, 3, 4};
int rund = 0;
for (int r = 0; r < 3; r++) {
rund++;
bool z = false;
for (int j = 0; j + 1 < 4 - r; j++)
if (v[j] > v[j + 1]) { swap(v[j], v[j + 1]); z = true; }
if (!z) break;
}
cout << rund;
Pokaż odpowiedź
vector<int> v = {2, 1, 3};
int p = 0;
for (int i = 1; i < 3; i++) {
int x = v[i], j = i - 1;
while (j >= 0 && v[j] > x) { v[j + 1] = v[j]; j--; p++; }
v[j + 1] = x;
}
cout << p;
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ę.
Sortowanie po swojemu: własna reguła porównania
Do tej pory sortowaliśmy „normalnie”: liczby od najmniejszej, słowa alfabetycznie. A co, jeśli zadanie każe ustawić liczby według ostatniej cyfry? Albo słowa od najkrótszego? Albo najpierw parzyste, potem nieparzyste? Wtedy dajesz sort własną regułę. To najważniejsza nowa umiejętność tej lekcji, więc pójdziemy bardzo powoli.
Reguła odpowiada na jedno pytanie
Wyobraź sobie, że sort to sędzia, który ustawia zawodników w szeregu. Sam nie wie, kto powinien stać wcześniej — za każdym razem pyta Twoją regułę o dwa elementy, a i b:
„Czy a ma stać PRZED b?”
Reguła odpowiada true (tak) albo false (nie). Sędzia zadaje to pytanie wiele razy, o różne pary, i na podstawie odpowiedzi ustawia wszystkich. Domyślna reguła sort to po prostu a < b: „a stoi przed b, gdy a jest mniejsze”. Dlatego bez reguły dostajesz kolejność rosnącą.
Jak zapisać regułę: lambda
Regułę piszemy jako trzeci argument sort, w specjalnym zapisie zwanym lambdą. Lambda to mały kawałek programu bez nazwy, napisany dokładnie w miejscu, w którym jest potrzebny. Oto reguła „większy przed mniejszym”:
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
[]Nawiasy kwadratowe mówią: „tu zaczyna się reguła”. Na razie zostawiamy je puste.
(int a, int b)Dwa porównywane elementy. Ich typ to typ elementów vectora: dla vector<int> piszesz int, dla napisów string.
{ return a > b; }Odpowiedź na pytanie „czy a przed b?”. return oddaje ją sędziemu — znasz to słowo z return 0; w main.
);Na końcu zamykamy nawias okrągły od sort( i stawiamy średnik. Łatwo o tym zapomnieć!
vector<int> v = {5, 2, 8, 1, 9};
sort(v.begin(), v.end(), [](int a, int b) {
return a > b; // a przed b, gdy a jest większe
});
for (auto x : v) cout << x << " ";
cout << "\n";
sort(v.begin(), v.end(), [](int a, int b) {
return a < b; // to samo co zwykłe sort
});
for (auto x : v) cout << x << " ";
cout << "\n";
Regułę można rozpisać na kilka linijek — tak jest czytelniej, gdy robi się dłuższa.
Przeczytaj pierwszą regułę na głos: „a ma stać przed b wtedy, gdy a jest większe od b”. Czyli większe liczby idą na przód — malejąco. Druga reguła to zwykła kolejność rosnąca, zapisana wprost.
Sztuczka do sprawdzania reguły: weź dwie konkretne liczby, np. a = 8 i b = 2, i zapytaj, co zwróci reguła. 8 > 2 to true, więc 8 stanie przed 2. Zgadza się z tym, co chcesz?
Według ostatniej cyfry — i co z remisami?
Ostatnia cyfra liczby to x % 10 (dla liczb nieujemnych). Reguła „mniejsza ostatnia cyfra wcześniej” wygląda tak: return a % 10 < b % 10;. Ale co, jeśli dwie liczby mają tę samą ostatnią cyfrę, jak 21 i 11? Reguła odpowiada wtedy „nie” w obie strony: ani 21 nie jest przed 11, ani 11 przed 21. Dla sędziego to remis — i sort może ustawić takie liczby w dowolnej kolejności. Nie ma żadnej gwarancji, że zostaną tak, jak były na wejściu.
Dlatego dobra reguła prawie zawsze ma drugie kryterium, które rozstrzyga remisy: „gdy ostatnie cyfry są takie same, mniejsza liczba wcześniej”.
vector<int> v = {23, 15, 42, 11, 30, 21, 5};
sort(v.begin(), v.end(), [](int a, int b) {
if (a % 10 != b % 10) {
return a % 10 < b % 10; // różne cyfry — decyduje cyfra
}
return a < b; // remis — decyduje cała liczba
});
for (auto x : v) cout << x << " ";
cout << "\n";
| ostatnia cyfra | liczby | w środku grupy |
|---|---|---|
| 0 | 30 | — |
| 1 | 11, 21 | 11 < 21 |
| 2 | 42 | — |
| 3 | 23 | — |
| 5 | 5, 15 | 5 < 15 |
if (pierwsze kryterium jest różne) return porównanie według pierwszego; potem if (drugie jest różne) return porównanie według drugiego; … a na końcu return porównanie według ostatniego;. Jak w słowniku: najpierw pierwsza litera, a dopiero przy remisie — następna. Tego wzoru będziesz używać cały czas.
Reguła może liczyć
W środku lambdy możesz pisać zwykły kod: zmienne, pętle, ify. Na przykład sortowanie według sumy cyfr: najpierw liczymy sumę cyfr a i sumę cyfr b (pętlą while, jak w lekcji o pętli while), a potem je porównujemy. Remis rozstrzyga sama liczba.
vector<int> v = {91, 8, 125, 44, 70, 17};
sort(v.begin(), v.end(), [](int a, int b) {
int sa = 0, sb = 0;
int x = a;
while (x > 0) { sa += x % 10; x /= 10; }
x = b;
while (x > 0) { sb += x % 10; x /= 10; }
if (sa != sb) return sa < sb;
return a < b;
});
for (auto x : v) cout << x << " ";
cout << "\n";
| liczba | suma cyfr |
|---|---|
| 70 | 7 |
| 8 | 8 |
| 17 | 8 |
| 44 | 8 |
| 125 | 8 |
| 91 | 10 |
Aż cztery liczby mają sumę cyfr 8 — o ich kolejności decyduje drugie kryterium: 8 < 17 < 44 < 125.
a i b w regule to kopie elementów — mógłbyś je zmieniać i vector by tego nie zauważył. Ale dla czytelności lepiej liczyć na osobnej zmiennej (tu x), tak jak w przykładzie.
Najbliżej zera
Odległość liczby od zera to jej wartość bezwzględna: abs(x). Reguła „bliżej zera wcześniej, a przy remisie (−3 i 3) ujemna wcześniej”:
vector<int> v = {3, -2, 2, -5, 0, -3};
sort(v.begin(), v.end(), [](int a, int b) {
if (abs(a) != abs(b)) return abs(a) < abs(b);
return a < b; // -3 przed 3
});
for (auto x : v) cout << x << " ";
cout << "\n";
Przy remisie −2 i 2 mają tę samą odległość od zera (2), więc rozstrzyga a < b: −2 jest mniejsze, staje pierwsze.
[&] — reguła, która widzi zmienne z main
Teraz chcemy sortować według odległości od liczby k, którą wczytaliśmy w main: abs(a - k). Problem: lambda z pustymi nawiasami [] nie widzi zmiennych z main — kompilator zgłosi błąd, że nie zna k. Rozwiązanie: wpisz w nawiasy kwadratowe znak &. Zapis [&] znaczy „reguła może zaglądać do zmiennych z miejsca, w którym ją napisano”. To ten sam znak co w for (auto &x : v) — tam też oznaczał „pracuj na oryginale, nie na kopii”.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> v(n);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end(), [&](int a, int b) {
if (abs(a - k) != abs(b - k)) return abs(a - k) < abs(b - k);
return a < b;
});
for (auto x : v) cout << x << " ";
cout << "\n";
return 0;
}
int k = 10;
vector<int> v = {1, 12, 8};
sort(v.begin(), v.end(), [](int a, int b) {
return abs(a - k) < abs(b - k); // BŁĄD: [] nie widzi k
});
Odległości od 10: 10 → 0, 8 → 2, 12 → 2, 15 → 5, 1 → 9, 20 → 10. Remis 8 i 12 rozstrzyga mniejsza liczba.
Słowa po swojemu
Dla vectora napisów reguła dostaje dwa napisy. Najczęstsze życzenie: od najkrótszego słowa, a słowa tej samej długości — alfabetycznie.
vector<string> s = {"pies", "kot", "zebra", "mysz", "lew", "ara"};
sort(s.begin(), s.end(), [](string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
});
for (auto x : s) cout << x << " ";
cout << "\n";
Trzyliterowe słowa (ara, kot, lew) idą pierwsze i między sobą alfabetycznie. Potem czteroliterowe, na końcu „zebra”.
Pamiętasz, że wielkie litery są przed małymi? Gdy chcesz porównywać słowa bez względu na wielkość liter, w regule zrób kopie a i b, zamień w nich wszystkie litery na małe (tolower w pętli) i porównaj kopie.
Najpierw parzyste, potem nieparzyste
Chcemy dwie grupy: najpierw wszystkie parzyste rosnąco, potem wszystkie nieparzyste rosnąco. Zapisujemy w zmiennych bool, czy a i b są parzyste. Jeśli jedna jest parzysta, a druga nie — wcześniej stoi ta parzysta. Jeśli obie są tego samego rodzaju — mniejsza wcześniej.
vector<int> v = {7, 4, -3, 10, 1, -6, 8};
sort(v.begin(), v.end(), [](int a, int b) {
bool pa = (a % 2 == 0);
bool pb = (b % 2 == 0);
if (pa != pb) return pa; // parzysta przed nieparzystą
return a < b;
});
for (auto x : v) cout << x << " ";
cout << "\n";
Linijka return pa; wymaga chwili namysłu. Wykonuje się tylko wtedy, gdy a i b są różnego rodzaju. Jeśli a jest parzyste (pa = true), to b nie jest — odpowiadamy „tak, a przed b”. Jeśli a jest nieparzyste (pa = false), to b jest parzyste — odpowiadamy „nie”.
Warunek a % 2 == 0 działa też dla liczb ujemnych. Gdybyś napisał a % 2 == 1, liczba −3 nie zostałaby uznana za nieparzystą, bo −3 % 2 to −1.
Żelazna zasada: dla równych — false
Reguła musi spełniać jeden warunek, którego kompilator nie sprawdzi za Ciebie: gdy pytasz o dwa elementy „równe” dla tej reguły, odpowiedź musi brzmieć false. W szczególności element nigdy nie może stać „przed samym sobą”. Dlatego w regule piszesz < albo >, a nigdy <= ani >=.
sort(v.begin(), v.end(), [](int a, int b) {
return a <= b; // ŹLE! Dla a == b odpowiada true
});
<= czasem działa na małych testach, a na dużych program nagle się wysypuje albo czyta pamięć spoza vectora — bez żadnego ostrzeżenia. Takie błędy są bardzo trudne do znalezienia. Druga podobna pułapka: reguła, która raz mówi „a przed b”, a za chwilę dla tej samej pary „b przed a” (np. losowa). Trzymaj się wzoru z ifami i ostrymi nierównościami, a wszystko będzie dobrze.
Reguła z nazwą
Długą regułę możesz zapisać w zmiennej i potem podawać jej nazwę. Typ takiej zmiennej jest bardzo skomplikowany, więc piszesz auto. Przydaje się, gdy tej samej reguły używasz kilka razy — albo po prostu dla czytelności.
auto wedlugDlugosci = [](string a, string b) {
if (a.size() != b.size()) return a.size() < b.size();
return a < b;
};
vector<string> owoce = {"kiwi", "banan", "figa", "jablko"};
vector<string> zwierzeta = {"wilk", "lis", "sowa", "bobr"};
sort(owoce.begin(), owoce.end(), wedlugDlugosci);
sort(zwierzeta.begin(), zwierzeta.end(), wedlugDlugosci);
for (auto x : owoce) cout << x << " ";
cout << "\n";
for (auto x : zwierzeta) cout << x << " ";
cout << "\n";
Tę samą regułę podajemy dwa razy — raz napisana, dwa razy użyta.
Uwaga na polskie litery: w napisie string litery takie jak „ś” czy „ó” zajmują po dwa znaki, więc size() słowa „ryś” to 4, a nie 3, i sortowanie według długości dałoby dziwne wyniki. Dlatego w zadaniach olimpijskich słowa składają się zwykle tylko z liter a–z.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {3, 1, 2};
sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {12, 5, 31, 24};
sort(v.begin(), v.end(), [](int a, int b) {
return a % 10 < b % 10;
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
vector<int> v = {-3, 2, -1};
sort(v.begin(), v.end(), [](int a, int b) {
if (abs(a) != abs(b)) return abs(a) < abs(b);
return a < b;
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
vector<string> s = {"ccc", "a", "bb"};
sort(s.begin(), s.end(), [](string a, string b) {
return a.size() > b.size();
});
for (auto x : s) cout << x << " ";
Pokaż odpowiedź
> — najdłuższe pierwsze.vector<int> v = {5, 2, 3, 4};
sort(v.begin(), v.end(), [](int a, int b) {
bool pa = (a % 2 == 0), pb = (b % 2 == 0);
if (pa != pb) return pa;
return a < b;
});
for (auto x : v) cout << x;
Pokaż odpowiedź
vector<int> v = {4, 9, 5};
sort(v.begin(), v.end(), [](int a, int b) {
return a % 3 < b % 3;
});
for (auto x : v) cout << x;
Pokaż odpowiedź
string s = "abc";
sort(s.begin(), s.end(), [](char a, char b) { return a > b; });
cout << s;
Pokaż odpowiedź
char.int k = 6;
vector<int> v = {1, 5, 9};
sort(v.begin(), v.end(), [&](int a, int b) {
return abs(a - k) < abs(b - k);
});
for (auto x : v) cout << x << " ";
Pokaż odpowiedź
& w nawiasach program by się nie skompilował.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ę.
Kilka kryteriów naraz: pary, sztuczka z minusem i stable_sort
Prawdziwe rankingi rzadko mają jedno kryterium. W konkursie wygrywa ten, kto ma więcej punktów, a przy remisie — ten, kto był szybszy. W dzienniku uczniowie stoją według nazwisk, a przy tych samych nazwiskach — według imion. W tej części ułożysz dane według dwóch i trzech kryteriów naraz.
Pary sortują się same
Przypomnienie z lekcji o parach: sort na vectorze par ustawia je najpierw według first, a przy remisie według second. To już są dwa kryteria — i nie trzeba pisać żadnej reguły. Wystarczy, że to, co ważniejsze, włożysz do first.
vector<pair<int, string>> p = {{12, "Ola"}, {11, "Jan"}, {12, "Ala"}, {10, "Ewa"}, {11, "Adam"}};
sort(p.begin(), p.end());
for (auto [wiek, imie] : p) cout << wiek << " " << imie << "\n";
Gdybyś chciał najpierw alfabetycznie, a przy tych samych imionach według wieku — zamieniłbyś kolejność w parze: pair<string, int>.
Zasada: główne kryterium na pierwsze miejsce. Wypisując, możesz pola ustawić w dowolnej kolejności.
Sztuczka z minusem
Ranking zawodów: więcej punktów wyżej (malejąco), a przy remisie krótszy czas wyżej (rosnąco). Pary porównują oba pola rosnąco, więc jak zrobić jedno malejąco? Sztuczka z lekcji o parach: zamiast punktów zapisz minus punkty. Rosnąco po −punktach to to samo co malejąco po punktach: −90 < −75 < −60. Przy wypisywaniu znowu zmieniasz znak.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> w(n); // (-punkty, czas)
for (auto &[mp, czas] : w) {
int punkty;
cin >> punkty >> czas;
mp = -punkty;
}
sort(w.begin(), w.end());
for (auto [mp, czas] : w) cout << -mp << " " << czas << "\n";
return 0;
}
Rozpakowanie z & w pętli wczytującej (auto &[mp, czas]) zapisuje wartości prosto do pary — znasz to z lekcji o parach.
Reguła dla par
Minus działa tylko dla liczb. A co, jeśli chcesz napisy w kolejności odwrotnej, albo para ma kryteria w „złej” kolejności, a nie chcesz jej przebudowywać? Wtedy piszesz regułę — dokładnie według wzoru z części 5. Para ma typ pair<string, int>, więc tak deklarujemy a i b. Żeby nie pisać długiego typu, można też użyć auto: [](auto a, auto b).
vector<pair<string, int>> r = {{"Ola", 75}, {"Jan", 90}, {"Ala", 75}, {"Ewa", 60}, {"Adam", 90}};
sort(r.begin(), r.end(), [](pair<string, int> a, pair<string, int> b) {
if (a.second != b.second) return a.second > b.second; // więcej punktów wyżej
return a.first < b.first; // remis: alfabetycznie
});
for (auto [imie, pkt] : r) cout << imie << " " << pkt << "\n";
vector<pair<string, int>> r = {{"Ola", 75}, {"Jan", 90}, {"Ala", 75}};
sort(r.begin(), r.end(), [](auto a, auto b) {
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
for (auto [imie, pkt] : r) cout << imie << " ";
cout << "\n";
Ta sama reguła, krócej zapisana. auto w nawiasach lambdy znaczy „typ taki, jak elementy vectora”.
Trzy kryteria
Ranking olimpiady: więcej punktów wyżej; przy remisie mniej prób wyżej; przy remisie i w tym — alfabetycznie. Trzy pola trzymamy w parze par: pair<string, pair<int, int>>, czyli (imię, (punkty, próby)). Reguła ma teraz dwa ify i ostatni return — schodki, jak w słowniku.
vector<pair<string, pair<int, int>>> z = {
{"Ola", {300, 5}}, {"Jan", {300, 3}}, {"Ewa", {250, 1}},
{"Ala", {300, 3}}, {"Igor", {250, 1}}
};
sort(z.begin(), z.end(), [](auto a, auto b) {
if (a.second.first != b.second.first)
return a.second.first > b.second.first; // 1. punkty malejąco
if (a.second.second != b.second.second)
return a.second.second < b.second.second; // 2. próby rosnąco
return a.first < b.first; // 3. imię alfabetycznie
});
for (auto x : z)
cout << x.first << " " << x.second.first << " " << x.second.second << "\n";
Ala i Jan remisują na punktach i na próbach — rozstrzyga alfabet. Ola ma tyle samo punktów, ale więcej prób, więc jest za nimi.
Zapis a.second.first szybko robi się nieczytelny. W części 7 poznasz wygodniejszy sposób: dane w kilku osobnych vectorach i sortowanie numerów.
stable_sort — remisy zostają w kolejności z wejścia
Pamiętasz z części 5: gdy reguła mówi „remis”, sort może ustawić takie elementy w dowolnej kolejności. Czasem jednak zadanie wymaga: „przy remisie zachowaj kolejność z wejścia”. Wtedy zamiast sort piszesz stable_sort — z tymi samymi argumentami. Stabilne sortowanie gwarantuje, że elementy równe dla reguły zostaną w takiej kolejności względem siebie, w jakiej były.
Przykład: lista uczniów w kolejności zapisów, każdy z numerem klasy. Chcemy pogrupować ich według klas, ale w każdej klasie zostawić kolejność zapisów. Reguła porównuje tylko klasy — a resztę załatwia stabilność.
vector<pair<string, int>> u = {{"Zosia", 2}, {"Adam", 1}, {"Ola", 2}, {"Bartek", 1}, {"Ala", 2}};
stable_sort(u.begin(), u.end(), [](auto a, auto b) {
return a.second < b.second; // tylko klasa!
});
for (auto [imie, klasa] : u) cout << klasa << " " << imie << "\n";
stable_sort z regułą, która porównuje tylko główne kryterium. Sposób 2: dopisz do danych numer z wejścia i użyj go jako ostatniego kryterium w regule — wtedy remisów w ogóle nie ma i wystarczy zwykłe sort. Oba dają ten sam wynik. Drugi sposób zobaczysz w części 7.
Punkty na płaszczyźnie
Punkty (x, y) to pary, więc sort bez reguły ustawi je „od lewej”: według x, a przy tym samym x — według y. Inne częste życzenie to sortowanie według odległości od początku układu (0, 0). Odległość to pierwiastek z x² + y², ale do porównywania pierwiastek nie jest potrzebny: większa odległość to większe x² + y². Liczymy więc same kwadraty — na liczbach całkowitych, bez błędów zaokrągleń.
vector<pair<int, int>> p = {{3, 4}, {-1, 1}, {0, 2}, {-5, 0}, {1, -1}};
sort(p.begin(), p.end(), [](auto a, auto b) {
long long da = 1LL * a.first * a.first + 1LL * a.second * a.second;
long long db = 1LL * b.first * b.first + 1LL * b.second * b.second;
if (da != db) return da < db;
return a < b; // remis: zwykłe porównanie par
});
for (auto [x, y] : p) cout << "(" << x << "," << y << ") ";
cout << "\n";
Kwadraty odległości: (3, 4) → 25, (−1, 1) → 2, (0, 2) → 4, (−5, 0) → 25, (1, −1) → 2.
Remisy rozstrzyga a < b — porównanie całych par, które już znasz: (−1, 1) przed (1, −1), bo −1 < 1; a (−5, 0) przed (3, 4).
1LL * zamienia mnożenie na long long: dla współrzędnych do miliarda sam kwadrat ma 18 cyfr i nie mieści się w int.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<pair<int, int>> p = {{2, 1}, {1, 5}, {2, 0}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << a << b << " ";
Pokaż odpowiedź
first (1 przed 2), a pary (2, 1) i (2, 0) według second.vector<pair<int, int>> p = {{-5, 30}, {-7, 40}, {-5, 20}};
sort(p.begin(), p.end());
for (auto [a, b] : p) cout << -a << ":" << b << " ";
Pokaż odpowiedź
vector<pair<string, int>> r = {{"a", 1}, {"b", 3}, {"c", 2}};
sort(r.begin(), r.end(), [](auto x, auto y) {
return x.second > y.second;
});
for (auto [s, k] : r) cout << s;
Pokaż odpowiedź
second malejąco: 3, 2, 1.vector<pair<int, char>> p = {{2, 'x'}, {1, 'y'}, {2, 'z'}, {1, 'w'}};
stable_sort(p.begin(), p.end(), [](auto a, auto b) {
return a.first < b.first;
});
for (auto [k, c] : p) cout << c;
Pokaż odpowiedź
first; wśród jedynek zostaje kolejność z wejścia (y przed w), wśród dwójek też (x przed z).vector<pair<int, char>> p = {{2, 'x'}, {1, 'y'}, {2, 'z'}, {1, 'w'}};
sort(p.begin(), p.end());
for (auto [k, c] : p) cout << c;
Pokaż odpowiedź
first = 1 decyduje znak, a 'w' < 'y'.vector<pair<int, int>> p = {{3, 4}, {1, 1}, {0, 2}};
sort(p.begin(), p.end(), [](auto a, auto b) {
return a.first * a.first + a.second * a.second
< b.first * b.first + b.second * b.second;
});
for (auto [x, y] : p) cout << x << y << " ";
Pokaż odpowiedź
vector<pair<string, int>> v = {{"Ola", 5}, {"Ala", 9}, {"Ola", 3}};
sort(v.begin(), v.end());
for (auto [s, k] : v) cout << s << k << " ";
Pokaż odpowiedź
vector<pair<int, int>> p = {{1, 2}, {1, 5}, {0, 9}};
sort(p.begin(), p.end(), [](auto a, auto b) {
if (a.first != b.first) return a.first > b.first;
return a.second > b.second;
});
for (auto [x, y] : p) cout << x << y << " ";
Pokaż odpowiedź
first (1 przed 0), przy remisie second (5 przed 2).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ę.
Sortujemy numery zamiast wartości: rekordy i miejsca w rankingu
Sortowanie ma jedną wadę: po nim nie wiadomo, kto był kim. Gdy posortujesz wzrost uczniów, dostaniesz ładny rząd liczb — ale czyj jest wzrost 152? W tej części poznasz sposób, który rozwiązuje ten problem raz na zawsze: zamiast wartości sortujemy numery. Przy okazji nauczysz się układać dane z wieloma polami i liczyć miejsca w rankingu z remisami.
Problem: kto jest kim?
Uczniowie stoją w kolejce, każdy ma swój numer 0, 1, 2, 3, a w vectorze w zapisaliśmy ich wzrost. Chcemy wiedzieć, kto jest najniższy, kto drugi… — czyli numery uczniów w kolejności od najniższego. Sposób z lekcji o parach: pary (wzrost, numer) i sort. Działa, ale przy wielu polach robi się nieczytelnie. Jest lepszy sposób.
Sortujemy numery, porównujemy wartości
Robimy vector numerów nr = {0, 1, 2, …, n − 1} i sortujemy ten vector — ale z regułą, która porównuje numery według wzrostu: „numer a stoi przed numerem b, gdy uczeń a jest niższy od ucznia b”, czyli w[a] < w[b]. Reguła musi widzieć vector w, więc ma [&]. Sam vector w się nie zmienia — przestawiają się tylko numery.
vector<int> w = {150, 142, 160, 138};
int n = w.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i; // 0 1 2 3
sort(nr.begin(), nr.end(), [&](int a, int b) {
return w[a] < w[b];
});
for (auto i : nr) cout << i << " ";
cout << "\n";
for (auto i : nr) cout << w[i] << " ";
cout << "\n";
Jak czytać wynik? nr[0] to numer najniższego ucznia, nr[1] — drugiego, i tak dalej. Wzrost k-tego w kolejności to w[nr[k]] — dwa nawiasy, jak w lekcji o vectorze przy permutacjach. W drugim wierszu wyniku wypisaliśmy wzrosty w kolejności numerów — wyszły posortowane, a w nadal jest nietknięty.
vector<int> nr(n); for (int i = 0; i < n; i++) nr[i] = i; a potem sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] < w[b]; });. a i b to numery, a porównujemy wartości pod tymi numerami.
Remis rozstrzyga numer
Gdy dwóch uczniów ma ten sam wzrost, reguła w[a] < w[b] mówi „remis” i sort może ich ustawić dowolnie. Najczęściej zadanie chce wtedy kolejności z wejścia — czyli mniejszy numer wcześniej. Dopisujemy więc drugie kryterium: return a < b;. To jest ten „sposób 2” z części 6 — zamiast stable_sort.
vector<int> w = {150, 142, 150, 138, 142};
int n = w.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) {
if (w[a] != w[b]) return w[a] < w[b];
return a < b; // ten sam wzrost — kolejność z kolejki
});
for (auto i : nr) cout << i << "(" << w[i] << ") ";
cout << "\n";
Uczniowie 1 i 4 mają po 142 cm — pierwszy jest 1, bo stał wcześniej. Tak samo 0 przed 2 przy 150 cm.
Rekordy w kilku vectorach
Teraz prawdziwy pożytek. Zawodnik ma imię, punkty i czas. Zamiast pakować to w pary par, trzymamy trzy osobne vectory: imie[i], pkt[i], czas[i] — wszystkie trzy pod numerem i opisują tego samego zawodnika. Taki zestaw nazywa się rekordem. Sortujemy numery z regułą o trzech kryteriach, a wypisujemy przez imie[nr[k]].
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<string> imie(n);
vector<int> pkt(n), czas(n);
for (int i = 0; i < n; i++) cin >> imie[i] >> pkt[i] >> czas[i];
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) {
if (pkt[a] != pkt[b]) return pkt[a] > pkt[b]; // więcej punktów
if (czas[a] != czas[b]) return czas[a] < czas[b]; // krótszy czas
return imie[a] < imie[b]; // alfabet
});
for (int k = 0; k < n; k++) {
int i = nr[k];
cout << k + 1 << ". " << imie[i] << " " << pkt[i] << " " << czas[i] << "\n";
}
return 0;
}
Porównaj z przykładem z części 6: reguła jest ta sama, ale zamiast a.second.first piszesz pkt[a]. Od razu widać, co porównujemy.
W pętli wypisującej najpierw zapisujemy int i = nr[k]; — numer zawodnika, który zajął miejsce k + 1. Dalej używamy już tylko i.
Ten sposób działa dla dowolnie wielu pól: dopisujesz kolejny vector i kolejny if w regule.
Miejsce każdego zawodnika — z remisami
Odwrotne pytanie: nie „kto jest k-ty”, tylko „które miejsce zajął zawodnik i”. W sporcie przy remisie zawodnicy dzielą miejsce (ex aequo), a następne miejsce jest pomijane: wyniki 90, 85, 85, 70 dają miejsca 1, 2, 2, 4. Algorytm: sortujemy numery malejąco według punktów i idziemy po kolei. Zawodnik na pozycji k dostaje miejsce k + 1 — chyba że ma tyle samo punktów co poprzedni; wtedy dostaje to samo miejsce co poprzedni. Miejsca zapisujemy w vectorze miejsce[i] pod numerem zawodnika, więc na koniec możemy je wypisać w kolejności z wejścia.
vector<int> pkt = {70, 85, 90, 85, 60, 90};
int n = pkt.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) {
if (pkt[a] != pkt[b]) return pkt[a] > pkt[b];
return a < b;
});
vector<int> miejsce(n);
for (int k = 0; k < n; k++) {
int i = nr[k];
if (k > 0 && pkt[i] == pkt[nr[k - 1]]) miejsce[i] = miejsce[nr[k - 1]];
else miejsce[i] = k + 1;
}
for (int i = 0; i < n; i++) cout << miejsce[i] << " ";
cout << "\n";
| k | nr[k] | punkty | jak poprzedni? | miejsce |
|---|---|---|---|---|
| 0 | 2 | 90 | — | 1 |
| 1 | 5 | 90 | tak | 1 |
| 2 | 1 | 85 | nie | 3 |
| 3 | 3 | 85 | tak | 3 |
| 4 | 0 | 70 | nie | 5 |
| 5 | 4 | 60 | nie | 6 |
Po dwóch zwycięzcach ex aequo następne miejsce to 3, a nie 2 — miejsce 2 „zużyli” obaj zwycięzcy razem.
Kompresja: numery zamiast wielkich liczb
Ostatnia sztuczka tej części jest bardzo olimpijska. Masz liczby 1000, 5, 1 000 000, 5, 70. Chciałbyś użyć tablicy liczników, ale liczby są ogromne. Ważna jest jednak tylko ich kolejność, nie wielkość. Zamieniamy więc każdą liczbę na jej numer wśród różnych wartości: najmniejsza dostaje 1, następna 2… Wynik: 3, 1, 4, 1, 2. Teraz wszystkie liczby są małe (najwyżej n) i tablica liczników znowu działa. Ta sztuczka nazywa się kompresją (albo przenumerowaniem).
vector<int> v = {1000, 5, 1000000, 5, 70};
int n = v.size();
vector<int> nr(n);
for (int i = 0; i < n; i++) nr[i] = i;
sort(nr.begin(), nr.end(), [&](int a, int b) { return v[a] < v[b]; });
vector<int> kod(n);
int numer = 0;
for (int k = 0; k < n; k++) {
if (k == 0 || v[nr[k]] != v[nr[k - 1]]) numer++; // nowa wartość
kod[nr[k]] = numer;
}
for (auto x : kod) cout << x << " ";
cout << "\n";
Zauważ, że to ten sam schemat co liczenie różnych wartości w części 3: numer rośnie, gdy wartość różni się od poprzedniej. Tyle że teraz idziemy po numerach, więc wiemy, komu ten numer przypisać.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> w = {5, 9, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] < w[b]; });
for (auto i : nr) cout << i;
Pokaż odpowiedź
vector<int> w = {5, 9, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] > w[b]; });
for (auto i : nr) cout << i;
Pokaż odpowiedź
vector<int> w = {4, 4, 1};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) {
if (w[a] != w[b]) return w[a] < w[b];
return a < b;
});
for (auto i : nr) cout << i;
Pokaż odpowiedź
vector<int> w = {7, 3, 8};
vector<int> nr = {2, 0, 1};
cout << w[nr[0]] << " " << w[nr[2]];
Pokaż odpowiedź
nr[0] = 2, więc w[2] = 8; nr[2] = 1, więc w[1] = 3.vector<int> p = {10, 30, 20, 30};
vector<int> nr = {1, 3, 2, 0}; // już posortowane malejąco
vector<int> m(4);
for (int k = 0; k < 4; k++) {
int i = nr[k];
if (k > 0 && p[i] == p[nr[k - 1]]) m[i] = m[nr[k - 1]];
else m[i] = k + 1;
}
for (auto x : m) cout << x << " ";
Pokaż odpowiedź
vector<int> v = {7, 3, 7, 10};
vector<int> nr = {1, 0, 2, 3}; // numery posortowane według v
vector<int> kod(4);
int c = 0;
for (int k = 0; k < 4; k++) {
if (k == 0 || v[nr[k]] != v[nr[k - 1]]) c++;
kod[nr[k]] = c;
}
for (auto x : kod) cout << x;
Pokaż odpowiedź
vector<string> s = {"kot", "a", "mysz"};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) {
return s[a].size() < s[b].size();
});
for (auto i : nr) cout << i;
Pokaż odpowiedź
vector<int> w = {170, 165, 180};
vector<int> nr = {0, 1, 2};
sort(nr.begin(), nr.end(), [&](int a, int b) { return w[a] > w[b]; });
cout << nr[1] << " " << w[nr[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ę.
Szukanie przez połowienie: lower_bound i upper_bound
W nieposortowanym vectorze, żeby sprawdzić, czy jest w nim liczba x, trzeba obejrzeć wszystkie elementy — tak działa find. W posortowanym da się to zrobić niesamowicie szybciej: w milionie liczb wystarczy zajrzeć do około 20 pudełek. W tej części poznasz pomysł połowienia i gotowe polecenia, które z niego korzystają.
Zabawa: zgadnij liczbę od 1 do 100
Ktoś pomyślał liczbę od 1 do 100. Możesz pytać „czy to x?”, a on odpowiada „tak”, „więcej” albo „mniej”. Jak zgadnąć jak najszybciej? Pytaj zawsze o środek przedziału, w którym może być liczba. Każda odpowiedź „więcej” albo „mniej” wyrzuca połowę możliwości: 100 → 50 → 25 → 12 → 6 → 3 → 1. Najwyżej 7 pytań! Strzelając po kolei 1, 2, 3, … mógłbyś potrzebować aż 100.
| pytanie | przedział | środek | odpowiedź (myślimy 71) |
|---|---|---|---|
| 1 | 1 … 100 | 50 | więcej |
| 2 | 51 … 100 | 75 | mniej |
| 3 | 51 … 74 | 62 | więcej |
| 4 | 63 … 74 | 68 | więcej |
| 5 | 69 … 74 | 71 | tak! |
Wyszukiwanie binarne w vectorze
Ten sam pomysł działa w posortowanym vectorze. Pilnujemy przedziału numerów od l do r, w którym może stać x. Patrzymy na środek s = (l + r) / 2. Jeśli v[s] == x — znaleźliśmy. Jeśli v[s] < x — x może stać tylko na prawo od s (bo na lewo są jeszcze mniejsze liczby), więc l = s + 1. W przeciwnym razie r = s − 1. Gdy przedział zrobi się pusty (l > r), x nie ma. Nazwa: wyszukiwanie binarne (binarne — bo za każdym razem dzielimy na dwie części).
vector<int> v = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int x = 23;
int l = 0, r = v.size() - 1;
bool jest = false;
while (l <= r) {
int s = (l + r) / 2;
cout << "l=" << l << " r=" << r << " s=" << s << " v[s]=" << v[s] << "\n";
if (v[s] == x) { jest = true; break; }
if (v[s] < x) l = s + 1; // x może być tylko na prawo
else r = s - 1; // x może być tylko na lewo
}
cout << (jest ? "jest" : "nie ma") << "\n";
Ile kroków najwyżej? Tyle, ile razy da się podzielić n na pół, zanim zostanie jedno pudełko. Dla tysiąca liczb — 10, dla miliona — 20, dla miliarda — 30. To jest właśnie log2n z części 4.
sort!
binary_search — jest czy nie ma?
Nie musisz pisać tej pętli za każdym razem. binary_search(v.begin(), v.end(), x) robi dokładnie to samo i zwraca true albo false. Przydaje się, gdy pytań jest dużo: sortujesz raz, a potem odpowiadasz na każde pytanie w kilkunastu krokach.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end()); // raz
while (q--) {
int x;
cin >> x;
if (binary_search(v.begin(), v.end(), x)) cout << "TAK\n";
else cout << "NIE\n";
}
return 0;
}
while (q--) to skrót: pętla wykona się q razy (q zmniejsza się po każdym sprawdzeniu, aż dojdzie do zera).
Dlaczego to takie ważne? Przy n = 100 000 liczb i q = 100 000 pytań, przeglądanie całego vectora przy każdym pytaniu to 10 miliardów kroków. Sortowanie i połowienie to kilka milionów.
lower_bound — pierwsze miejsce, gdzie x by pasował
binary_search mówi tylko „jest” albo „nie ma”. Często chcemy wiedzieć więcej: gdzie stoi x i ile jest liczb mniejszych od niego. Do tego służy lower_bound(v.begin(), v.end(), x). Zwraca strzałkę na pierwszy element, który jest ≥ x — czyli na pierwsze miejsce, w które dałoby się wstawić x, nie psując porządku. Jeśli wszystkie elementy są mniejsze od x, zwraca end().
Jak z każdej strzałki, numer dostajesz, odejmując v.begin(). I tu jest piękna rzecz: ten numer to jednocześnie liczba elementów mniejszych od x — bo wszystkie stoją na lewo od tego miejsca.
upper_bound — pierwsze miejsce ZA wszystkimi x
Brat bliźniak: upper_bound(v.begin(), v.end(), x) zwraca strzałkę na pierwszy element, który jest > x (ściśle większy). Czyli przeskakuje wszystkie elementy równe x. Numer tego miejsca to liczba elementów ≤ x.
vector<int> v = {2, 4, 4, 4, 7, 9};
for (int x : {4, 5, 1, 10}) {
int lo = lower_bound(v.begin(), v.end(), x) - v.begin();
int up = upper_bound(v.begin(), v.end(), x) - v.begin();
cout << "x=" << x << ": mniejszych " << lo
<< ", co najwyzej x " << up
<< ", rownych " << up - lo << "\n";
}
Pętla for (int x : {4, 5, 1, 10}) to wygodny sposób, żeby sprawdzić kilka wartości po kolei — pętla „dla każdego” po liście w klamrach.
Gdy x nie ma w vectorze (5, 1, 10), obie strzałki pokazują to samo miejsce — i różnica wynosi 0.
Ściąga: liczenie jednym odejmowaniem
Wszystkie te wzory zakładają, że v jest posortowany rosnąco. Dla wygody oznaczmy L(x) = lower_bound(v.begin(), v.end(), x) - v.begin() i U(x) = upper_bound(v.begin(), v.end(), x) - v.begin():
| pytanie | odpowiedź | dla v = 2 4 4 4 7 9 |
|---|---|---|
| ile elementów < x | L(x) | x = 7: 4 |
| ile elementów ≤ x | U(x) | x = 7: 5 |
| ile elementów == x | U(x) - L(x) | x = 4: 3 |
| ile elementów > x | n - U(x) | x = 4: 2 |
| ile elementów ≥ x | n - L(x) | x = 4: 5 |
| ile elementów w przedziale [a, b] | U(b) - L(a) | [3, 8]: 4 |
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> v(n);
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
while (q--) {
int a, b;
cin >> a >> b;
int ile = upper_bound(v.begin(), v.end(), b) - lower_bound(v.begin(), v.end(), a);
cout << ile << "\n";
}
return 0;
}
Po sortowaniu: 1 3 9 9 15 20 27. W przedziale [5, 15] leżą 9, 9 i 15 — trzy liczby (końce przedziału się liczą). W [10, 14] nie ma żadnej. W [0, 100] — wszystkie.
Różnica dwóch strzałek to od razu liczba — nie trzeba odejmować v.begin() osobno od każdej.
Najbliższa wartość
Masz cennik (posortowany) i chcesz znaleźć cenę najbliższą x. lower_bound(x) pokazuje najmniejszą cenę ≥ x — to jeden kandydat. Drugi kandydat stoi tuż przed nim: największa cena < x. Trzeba porównać obu (uważając, żeby nie wyjść poza vector).
vector<int> c = {10, 25, 40, 60, 95};
for (int x : {30, 34, 5, 120}) {
int i = lower_bound(c.begin(), c.end(), x) - c.begin();
int najlepsza;
if (i == (int)c.size()) najlepsza = c[i - 1]; // wszystkie mniejsze
else if (i == 0) najlepsza = c[0]; // wszystkie większe
else if (x - c[i - 1] <= c[i] - x) najlepsza = c[i - 1];
else najlepsza = c[i];
cout << x << " -> " << najlepsza << "\n";
}
Dla x = 30: lower_bound pokazuje 40 (numer 2), a przed nim stoi 25. Odległości: 5 i 10 — wygrywa 25.
Znak <= w porównaniu odległości sprawia, że przy remisie (np. x = 50: 40 i 60) wybieramy tańszą cenę.
Dwa brzegi trzeba obsłużyć osobno: gdy i = 0, przed nim nikogo nie ma; gdy i = n, c[i] nie istnieje.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> v = {1, 3, 5, 7};
cout << lower_bound(v.begin(), v.end(), 4) - v.begin();
Pokaż odpowiedź
vector<int> v = {1, 3, 5, 7};
cout << upper_bound(v.begin(), v.end(), 5) - v.begin();
Pokaż odpowiedź
vector<int> v = {2, 4, 4, 4, 7};
cout << upper_bound(v.begin(), v.end(), 4) - lower_bound(v.begin(), v.end(), 4);
Pokaż odpowiedź
vector<int> v = {1, 3, 5, 7};
cout << binary_search(v.begin(), v.end(), 6);
Pokaż odpowiedź
false wypisuje się jako 0.vector<int> v = {1, 3, 5, 7};
cout << lower_bound(v.begin(), v.end(), 10) - v.begin();
Pokaż odpowiedź
end() — numer 4, czyli rozmiar vectora.vector<int> v = {1, 3, 5, 7};
cout << upper_bound(v.begin(), v.end(), 6) - lower_bound(v.begin(), v.end(), 3);
Pokaż odpowiedź
vector<int> v = {1, 3, 5, 7};
cout << *lower_bound(v.begin(), v.end(), 4);
Pokaż odpowiedź
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
int x = 1, l = 0, r = 7, kroki = 0;
while (l <= r) {
kroki++;
int s = (l + r) / 2;
if (v[s] == x) break;
if (v[s] < x) l = s + 1;
else r = s - 1;
}
cout << kroki;
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ę.
Najpierw posortuj, potem bierz po kolei: pomysły zachłanne
Wiele zadań olimpijskich rozwiązuje się według tego samego przepisu: posortuj dane w odpowiedniej kolejności, a potem bierz po kolei to, co w danej chwili wygląda najlepiej. Taki sposób myślenia nazywa się zachłannym — jak ktoś zachłanny, bierzemy od razu najlepszy kąsek i nigdy nie wracamy do wcześniejszych decyzji. Znasz już jeden przykład z lekcji o parach: wybór jak największej liczby wykładów. W tej części poznasz kolejne.
Jak najwięcej rzeczy za budżet
Masz B złotych i listę cen prezentów. Chcesz kupić jak najwięcej prezentów (każdy co najwyżej raz). Pomysł: kupuj od najtańszych, dopóki starcza pieniędzy. Dlaczego to najlepsze? Załóżmy, że ktoś kupił jakiś drogi prezent, a pominął tańszy. Gdyby zamienił drogi na tańszy, miałby tyle samo prezentów i więcej pieniędzy. Zatem zawsze opłaca się brać najtańsze.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long budzet;
cin >> n >> budzet;
vector<int> c(n);
for (auto &x : c) cin >> x;
sort(c.begin(), c.end()); // od najtańszego
int ile = 0;
long long wydane = 0;
for (auto x : c) {
if (wydane + x > budzet) break; // na ten już nie stać
wydane += x;
ile++;
}
cout << ile << " " << wydane << "\n";
return 0;
}
Po sortowaniu: 7 9 12 15 20 35. Kupujemy 7, 9, 12 i 15 (razem 43). Na 20 już nie starcza (43 + 20 = 63 > 50), a skoro nie stać nas na 20, to na droższe 35 tym bardziej — dlatego break.
Kolejka do kasy: kto pierwszy?
Do jednej kasy przyszło jednocześnie n klientów. Obsługa klienta trwa ti minut. Każdy klient czeka, aż skończy się jego obsługa. W jakiej kolejności obsługiwać, żeby suma czasów czekania wszystkich klientów była najmniejsza? Odpowiedź: od najkrótszego. Krótka obsługa na początku opóźnia wszystkich za nią tylko trochę, a długa — bardzo.
| kolejność | klienci kończą po | suma czekania |
|---|---|---|
| 5, 1, 3 | 5, 6, 9 | 20 |
| 3, 5, 1 | 3, 8, 9 | 20 |
| 1, 3, 5 (od najkrótszego) | 1, 4, 9 | 14 ← najmniej |
| 5, 3, 1 (od najdłuższego) | 5, 8, 9 | 22 ← najwięcej |
vector<int> t = {5, 1, 3, 2, 8};
sort(t.begin(), t.end()); // 1 2 3 5 8
long long zegar = 0, suma = 0;
for (auto x : t) {
zegar += x; // ten klient kończy w chwili zegar
suma += zegar;
}
cout << suma << "\n";
Klienci kończą po 1, 3, 6, 11 i 19 minutach: 1 + 3 + 6 + 11 + 19 = 40.
Zmienna zegar to suma prefiksowa z lekcji o vectorze — czas, który upłynął do końca obsługi bieżącego klienta.
Łódki: najcięższy z najlżejszym
Ludzie przepływają rzekę łódkami. Łódka mieści najwyżej dwie osoby o łącznej wadze najwyżej L. Ile najmniej łódek potrzeba? Pomysł: posortuj wagi i ustaw dwa wskaźniki — i na najlżejszej osobie, j na najcięższej. Najcięższy i tak musi czymś popłynąć. Jeśli zmieści się z najlżejszym — płyną razem (i++, j--). Jeśli nie — najcięższy nie zmieści się z nikim, więc płynie sam (j--). W obu przypadkach zużyliśmy jedną łódkę.
vector<int> w = {70, 50, 80, 30, 60, 90};
int L = 120;
sort(w.begin(), w.end()); // 30 50 60 70 80 90
int i = 0, j = w.size() - 1, lodek = 0;
while (i <= j) {
if (i < j && w[i] + w[j] <= L) {
cout << w[i] << "+" << w[j] << " ";
i++;
} else {
cout << w[j] << " ";
}
j--;
lodek++;
}
cout << "\n" << lodek << "\n";
| łódka | w[i] | w[j] | razem ≤ 120? | płynie |
|---|---|---|---|---|
| 1 | 30 | 90 | 120 tak | 30 i 90 |
| 2 | 50 | 80 | 130 nie | 80 sam |
| 3 | 50 | 70 | 120 tak | 50 i 70 |
| 4 | 60 | 60 | i == j | 60 sam |
W łódce 2 najcięższy z pozostałych (80) nie mieści się nawet z najlżejszym (50) — więc z nikim się nie zmieści i płynie sam. W łódce 4 wskaźniki spotkały się na jednej osobie (i == j) — ona też płynie sama. Warunek i < j w ifie pilnuje, żeby nie posadzić osoby „samej ze sobą”.
Mnożenie w parach: największy z największym
Masz dwie listy po n liczb (nieujemnych): a — ile sztuk każdego produktu możesz sprzedać, b — ceny, jakie dają różni kupcy. Każdy produkt sprzedajesz innemu kupcowi. Jak połączyć je w pary, żeby zarobić jak najwięcej (suma iloczynów)? Intuicja: najwięcej sztuk sprzedaj najlepiej płacącemu. Po sortowaniu obu list rosnąco łączymy a[i] z b[i] — największy z największym. A żeby wyszło najmniej, jedną listę sortujemy rosnąco, a drugą malejąco.
vector<long long> a = {3, 1, 2};
vector<long long> b = {10, 30, 20};
sort(a.begin(), a.end()); // 1 2 3
sort(b.begin(), b.end()); // 10 20 30
long long maks = 0, mini = 0;
int n = a.size();
for (int i = 0; i < n; i++) {
maks += a[i] * b[i]; // największy z największym
mini += a[i] * b[n - 1 - i]; // największy z najmniejszym
}
cout << maks << " " << mini << "\n";
Najwięcej: 1·10 + 2·20 + 3·30 = 140. Najmniej: 1·30 + 2·20 + 3·10 = 100.
Argument zamiany: jeśli gdzieś mniejsze a stoi z większym b, a większe a z mniejszym b, to zamiana tych dwóch b nie zmniejsza sumy. Sprawdź na liczbach: 1·30 + 3·10 = 60, a po zamianie 1·10 + 3·30 = 100.
Dwie posortowane listy: ciastka dla dzieci
Każde dziecko ma apetyt — minimalny rozmiar ciastka, które je zadowoli. Masz ciastka różnej wielkości; każde dziecko dostaje najwyżej jedno ciastko. Ile najwięcej dzieci zadowolisz? Sortujemy obie listy. Idziemy po ciastkach od najmniejszego: jeśli bieżące ciastko zadowala dziecko z najmniejszym apetytem spośród niezadowolonych — dajemy je; jeśli nie — to ciastko jest za małe dla wszystkich pozostałych dzieci, więc je pomijamy.
vector<int> apetyt = {5, 2, 8, 3};
vector<int> ciastko = {4, 1, 3, 9, 2};
sort(apetyt.begin(), apetyt.end()); // 2 3 5 8
sort(ciastko.begin(), ciastko.end()); // 1 2 3 4 9
int d = 0; // pierwsze niezadowolone dziecko
for (auto c : ciastko) {
if (d < (int)apetyt.size() && c >= apetyt[d]) {
cout << "ciastko " << c << " -> dziecko z apetytem " << apetyt[d] << "\n";
d++;
}
}
cout << d << "\n";
Ciastko 1 jest za małe nawet dla najmniej wymagającego dziecka (2) — pomijamy. 2 → dziecko 2, 3 → dziecko 3. Ciastko 4 nie wystarczy dziecku z apetytem 5 — pomijamy. 9 → dziecko 5. Dla dziecka z apetytem 8 zabrakło ciastek.
Dlaczego dajemy ciastko najmniej wymagającemu? Bo większe ciastka warto zostawić dla bardziej wymagających dzieci.
Kiedy zachłanność zawodzi
Uwaga: nie każdy „oczywisty” pomysł zachłanny jest dobry. Wydajesz resztę monetami o nominałach 1, 3 i 4 i chcesz użyć jak najmniej monet. Zachłannie: zawsze największa moneta, która się mieści. Dla 6 zł: 4 + 1 + 1 — trzy monety. A wystarczą dwie: 3 + 3! Zachłanność zawiodła, bo nie da się tu przeprowadzić argumentu zamiany. Dlatego zanim zaufasz pomysłowi zachłannemu, sprawdź go na kilku małych przykładach — najlepiej porównując z rozwiązaniem, które sprawdza wszystkie możliwości.
Najpierw odpowiedz w myślach — narysuj sobie vector na kartce jako rząd pudełek z numerami i śledź program linijka po linijce — a dopiero potem kliknij „Pokaż odpowiedź”.
vector<int> c = {7, 2, 5, 3};
sort(c.begin(), c.end());
int b = 10, ile = 0;
for (auto x : c) {
if (x > b) break;
b -= x;
ile++;
}
cout << ile;
Pokaż odpowiedź
vector<int> t = {3, 1, 2};
sort(t.begin(), t.end());
int z = 0, s = 0;
for (auto x : t) { z += x; s += z; }
cout << s;
Pokaż odpowiedź
vector<int> w = {60, 40, 70, 30};
sort(w.begin(), w.end());
int i = 0, j = 3, ile = 0;
while (i <= j) {
if (i < j && w[i] + w[j] <= 100) i++;
j--;
ile++;
}
cout << ile;
Pokaż odpowiedź
vector<int> a = {1, 2}, b = {3, 4};
cout << a[0] * b[0] + a[1] * b[1] << " " << a[0] * b[1] + a[1] * b[0];
Pokaż odpowiedź
vector<int> ap = {1, 2, 3}, c = {1, 1};
int d = 0;
for (auto x : c)
if (d < 3 && x >= ap[d]) d++;
cout << d;
Pokaż odpowiedź
int reszta = 6, monet = 0;
int nom[3] = {4, 3, 1};
for (int k = 0; k < 3; k++) {
while (reszta >= nom[k]) { reszta -= nom[k]; monet++; }
}
cout << monet;
Pokaż odpowiedź
vector<int> v = {1, 9, 3, 7};
sort(v.begin(), v.end());
int najw = 0;
for (int i = 0; i < 2; i++) najw = max(najw, v[i] + v[3 - i]);
cout << najw;
Pokaż odpowiedź
vector<int> t = {4, 4, 1};
sort(t.begin(), t.end());
int z = 0, s = 0;
for (auto x : t) { z += x; s += z; }
cout << z << " " << s;
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ę.
Baza zadań: sortowanie w praktyce
Znasz już wszystko, co potrzebne: sort rosnąco i malejąco na vectorze, tablicy i napisie, k-ty element i medianę, grupy równych wartości, unique i najbliższych sąsiadów, cztery metody sortowania ręcznego, własne reguły z lambdą, kilka kryteriów naraz i stable_sort, sortowanie numerów, miejsca w rankingu i kompresję, lower_bound i upper_bound, a na koniec pomysły zachłanne. 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 czy vector. 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 sortowania
Rosnąco i malejąco
sort(v.begin(), v.end()); sort(t, t + n); // tablica sort(v.rbegin(), v.rend()); sort(v.begin(), v.end(), greater<int>());
Napisy — alfabetycznie, ale wielkie litery przed małymi, a „10” przed „9”.
Adresy w posortowanym
v[0] v[n - 1] // min, max v[k - 1] v[n - k] // k-ty od dołu, od góry v[n / 2] // mediana (n nieparzyste) (v[n/2 - 1] + v[n/2]) / 2.0
Remis na granicy: wszyscy z wynikiem ≥ v[n - k].
Grupy i unique
i = 0;
while (i < n) { j = i;
while (j < n && v[j] == v[i]) j++;
// grupa v[i..j-1]
i = j; }
v.erase(unique(v.begin(), v.end()), v.end());
Najpierw sort! Najbliżsi to zawsze sąsiedzi: v[i + 1] - v[i].
Sortowanie ręczne
wybieranie: min z [i..n-1] na miejsce i bąbelki: swap sąsiadów, runda po rundzie wstawianie: x wsuwa się w lewą część zliczanie: licznik[x]++, potem wypisz
Dwie pętle ≈ n·n — dobre do kilku tysięcy. sort ≈ n·log n.
Własna reguła
sort(v.begin(), v.end(), [](int a, int b) {
if (kl(a) != kl(b)) return kl(a) < kl(b);
return a < b;
});
„Czy a przed b?” Dla równych — false, więc nigdy <=. Zmienne z main: [&].
Kilka kryteriów
pair: najpierw first, potem second
(-punkty, czas) // minus = malejąco
[](auto a, auto b) { ... }
stable_sort(...) // remisy jak na wejściu
Główne kryterium na pierwsze miejsce pary albo do pierwszego ifa reguły.
Numery i rankingi
vector<int> nr(n); nr[i] = i;
sort(nr..., [&](int a, int b) {
return w[a] < w[b]; });
miejsce: jak poprzedni → to samo
kompresja: nowa wartość → numer++
k-ty w kolejności to nr[k], jego wartość — w[nr[k]].
Szukanie i zachłanność
binary_search(b, e, x) // jest? lower_bound(...) - v.begin() // ile < x upper_bound(...) - v.begin() // ile ≤ x [a, b]: U(b) - L(a)
Zachłannie: posortuj i bierz po kolei; sprawdź argumentem zamiany.
sort. 2) Zdecyduj, według czego sortować: wartości, kilku kryteriów, a może numerów? Gdy po sortowaniu trzeba wiedzieć, kto był kim — sortuj numery albo pary (wartość, numer). 3) Ustal, co robić z remisami — zadanie zwykle to mówi. 4) Sprawdź ograniczenia: n do kilku tysięcy pozwala na dwie pętle, n do 100 000 — tylko na sort i połowienie. 5) Przetestuj skrajności: jeden element, wszystkie równe, liczby ujemne, ogromne wartości (long long!).
Rozgrzewka · zadania 1–10
Jeden pomysł naraz: szereg na WF-ie, mały słownik, skarpetki do pary, ciąg arytmetyczny, najmniejszy wolny numer, brązowy medal, najcieplejsze dni, patyczki na trójkąt, liczba Kaprekara i pary butów.
Średnie · zadania 11–20
Kilka sztuczek naraz: dwa rankingi, sortowanie według częstości, indeks h, wyrównywanie wież, największy obwód, mediana na bieżąco, pary o różnicy k, zgrana drużyna, wieże z klocków i śpiewne słowa.
Trudne · zadania 21–28
Największa liczba ze sklejenia, kwota nie do zapłacenia, suma odległości, kary za czekanie, trójki o sumie zero, wyrównana grupa, książki na półce — a na koniec wielki finał: ranking olimpiady.