Обход массива - Язык программирования C++ для спортивного программирования
Неделя 4Массивы и Векторы, Обход массива, Основы временной сложности
Обход массива
Приёмы обхода вектора: суммы, количества, наибольшее и наименьшее, индекс лучшего элемента, линейный поиск, два прохода и второй максимум, соседи и серии, оба конца (палиндромы, разворот через swap) и циклические сдвиги.
Теория
Урок 3 из 8
27 мин чтения
Вопросов: 6
Обойти вектор — значит посетить его элементы один за другим, обычно циклом от
индекса 0 до n - 1. Счётчики, суммы и максимумы недели 3 работают и на векторе,
но вектор умеет то, чего не умеет поток чисел: смотреть на числа дважды,
смотреть на элемент вместе с его соседом, начинать с обоих концов и
переставлять элементы на новые места. В этом уроке разберём эти приёмы один
за другим.
Суммы, количества и наибольшее
Циклы недели 3, записанные для вектора:
С размахом чисел, mx - mn, нужно быть осторожнее: для чисел от −10⁹ до 10⁹
он может достигать 2 · 10⁹ — слишком много для int. Когда числа могут так
далеко отстоять друг от друга, читайте их в vector<long long> и делайте mx и
mn тоже long long: max и min хотят, чтобы оба их значения были одного
типа, поэтому max(mx, a[i]) с mx типа long long и a[i] типа int не
скомпилируется.
Где он? Храним индекс
Чтобы сообщить, где стоит наибольший элемент, храните вместо его значения
его индекс best. Значение всегда под рукой — это a[best]:
Наибольший — и где он стоит
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {4, 9, 2, 9, 5};
9 int n = a.size();
10 int best = 0;
11 for (int i = 1; i < n; i++) {
12 if (a[i] > a[best]) {
13 best = i;
14 }
15 }
16 cout << a[best] << " " << best + 1 << "\n";
17 return 0;
18}
Пять чисел
строка 8
Наибольшее значение встречается дважды. Какую позицию сообщит программа?
a5 ячеек
4
9
2
9
5
0
1
2
3
4
n—best—i—
нажми пуск
1 / 19
дальше
Практика: Суммы, Количества и Экстремумы
Суммы, количества, наименьшее и наибольшее, где они стоят и что с ними делает второй проход.
С > равное значение не отнимает первенство, поэтому best остаётся на
первом наибольшем элементе; с >= он переходит на последний. Обычно в
условии сказано, какой нужен («если таких несколько, выведите первый»).
Линейный поиск
«Где x?» — тот же цикл: смотрим на элементы слева и останавливаемся на первом
совпадении. -1 означает «не найдено», потому что индекса −1 не бывает:
Это линейный поиск. Без break цикл идёт дальше, и pos в итоге указывает
на последнее совпадение.
Два прохода
Для некоторых вопросов нужно знать что-то обо всём векторе, прежде чем можно
судить о любом отдельном элементе. На вопрос «у каких игроков лучший результат?»
нельзя ответить про первого игрока, пока не известны все результаты. Поэтому
пройдите по вектору дважды: первый проход находит лучший результат, второй
сравнивает с ним каждый элемент.
Даны результаты n игроков. Выведите лучший результат, а на следующей строке —
позиции (считая с 1) всех игроков, которые его получили.
Ввод
Вывод
По той же схеме решаются «сколько элементов равны максимуму», «сколько операций
сделают каждый элемент равным максимуму» или «замените каждый минимум на максимум,
а каждый максимум — на минимум». В последней задаче решайте судьбу каждого
элемента один раз, через if / else if: два отдельных if тут же
превратили бы новый максимум обратно в минимум.
Второй максимум — это наибольший элемент, когда наибольший выброшен, а
«выброшен» может означать две разные вещи:
Числа
Выбросить позициюbest
Выбросить все элементы, равные максимуму
9 9 5
9 — другая 9 никуда не делась
5 — наибольшее другое значение
9 7 5
7
7
Первый вариант — это второй проход с if (i != best), второй — с
if (a[i] != mx). Прочитайте условие и его примеры, чтобы понять, какой из них
имеется в виду, — когда все значения различны, оба дают один и тот же ответ.
Соседи
Во многих вопросах каждый элемент сравнивается с соседним: отсортирован ли
вектор, где он возрастает, какой длины серии одинаковых значений? У элемента
a[i] есть правый сосед a[i + 1], только пока i + 1 < n:
Или сравнивайте с левым соседом и начинайте цикл с 1:
for (int i = 1; i < n; i++) с a[i - 1]. Так или иначе, у n элементов
n - 1 пар соседей. В отсортированном векторе равные значения стоят рядом,
поэтому, посчитав места, где a[i] != a[i - 1] (и прибавив единицу за первый
элемент), мы посчитаем различные значения.
Серии. Серия — это участок подряд идущих элементов, каждый из которых
проходит одну и ту же проверку. Храните длину серии, которая заканчивается на
текущем элементе, и лучшую длину на данный момент:
Соседи: самая длинная серия возрастающих чисел
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {2, 5, 7, 3, 6, 8, 9};
9 int n = a.size();
10 int run = 1, best = 1;
11 for (int i = 1; i < n; i++) {
12 if (a[i] > a[i - 1]) {
13 run++;
14 } else {
15 run = 1;
16 }
17 best = max(best, run);
18 }
19 cout << best << "\n";
20 return 0;
21}
Семь чисел
строка 8
Самая длинная серия, где каждое число больше предыдущего: 3 6 8 9, четыре числа.
a7 ячеек
2
5
7
3
6
8
9
0
1
2
3
4
5
6
n—run—best—i—
нажми пуск
1 / 36
Серия растёт, пока проверка выполняется, и начинается заново с 1, когда она не
выполняется; best обновляется на каждом шаге, поэтому серия, которая доходит до
конца вектора, не теряется. Проверка вообще не обязана касаться соседа:
Дано количество осадков за n дней, в миллиметрах. Выведите наибольшее число
дней подряд, в которые шёл дождь (осадков больше 0).
Ввод
Вывод
Здесь серия начинается с 0, а не с 1: сухой день сбрасывает её в 0, и если дождя
не было ни разу, ответ — 0.
Шагомер в телефоне делает ровно это каждый вечер. Станьте его циклом: найдите
лучший день недели по его индексу, а потом самую длинную серию дней с выполненной
целью.
Неделя шаговпопробуй!
Сразу с обоих концов
Элемент и его зеркальный элемент — a[i] и a[n - 1 - i] — стоят на
одинаковом расстоянии от двух концов. Вектор — палиндром, если каждый
элемент равен своему зеркальному; достаточно проверить первую половину, потому
что вторая половина проверяет те же пары ещё раз:
Чтобы развернуть вектор на месте, поменяйте каждый элемент местами с
зеркальным. Удобнее всего это сделать двумя индексами: i начинает с левого
конца, j — с правого, и они идут навстречу друг другу, пока не встретятся.
swap(a[i], a[j]) меняет два значения местами:
Два конца идут навстречу друг другу
C++
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5 ios_base::sync_with_stdio(false);
6 cin.tie(NULL);
7
8 vector<int> a = {3, 8, 1, 9, 4, 7};
9 int i = 0, j = a.size() - 1;
10 while (i < j) {
11 swap(a[i], a[j]);
12 i++;
13 j--;
14 }
15 for (int x : a) {
16 cout << x << " ";
17 }
18 cout << "\n";
19 return 0;
20}
Шесть чисел
строка 8
Разворачиваем вектор на месте: первый и последний меняются местами, потом второй и предпоследний, и так далее.
a6 ячеек
3
8
1
9
4
7
0
1
2
3
4
5
i—j—x—
нажми пуск
1 / 29
При нечётном числе элементов средний элемент сам себе зеркальный и остаётся на
месте. Чтобы развернуть только часть от l-го до r-го элемента, начните с
i = l - 1 и j = r - 1 — больше ничего не меняется.
swap — это сокращение для трёх присваиваний через запасную переменную:
int t = a[i]; a[i] = a[j]; a[j] = t;. Просто a[i] = a[j]; a[j] = a[i]; не
сработает: после первой строки старое a[i] потеряно, и в обеих ячейках
оказывается одно и то же значение.
Теперь станьте циклом сами. Разверните каждый ряд как можно меньшим числом
обменов — каждый обмен должен ставить две карты на их окончательные места:
Отразите рядпопробуй!
Переставляем по кругу: сдвиги
Циклический сдвиг вправо на одно место передвигает каждый элемент на одно
место вправо, а последний элемент переходит в начало: 1 2 3 4 становится
4 1 2 3. Чтобы его напечатать, выведите a[n - 1], а затем a[0] … a[n - 2].
Чтобы сделать его на месте, сохраните последний элемент и сдвигайте остальные,
начиная с правого конца:
Направление важно. Если идти слева, a[1] = a[0] затёрло бы a[1] раньше, чем
оно успело сдвинуться, и a[0] в итоге оказалось бы скопировано в каждую ячейку.
Сдвиг на k мест проще всего сделать со вторым вектором: элемент с индексом
i переходит на индекс i + k, а индекс, который заходит за конец, переносится
в начало — ровно это и делает % n:
n гостей сидят за круглым столом, и их имена — числа. Каждый пересаживается на
k мест вправо (последнее место соседствует с первым). Выведите числа по местам
после пересадки.
Ввод
Вывод
Гость 50 с индексом 4 переходит на индекс (4 + 3) % 7 = 0: за конец и по кругу в
начало. Каждый элемент ставится на место один раз — n шагов при любом k.
(Сдвиг на одно место, повторённый k раз, даёт тот же ответ, но занимает
n · k шагов; почему это важно, — в следующем уроке.)
Проверьте себя
А вы знали?
В 2014 году в OpenSSL — коде, который защищает значительную часть
зашифрованных соединений в интернете, — нашли ошибку под названием Heartbleed.
Компьютер мог отправить короткое сообщение и заявить, что оно длинное; сервер
отправлял назад столько байтов, сколько ему сказали, читая далеко за концом
настоящего сообщения, — и выдавал всё, что лежало там в памяти, включая пароли и
секретные ключи. Исправление свелось к одной проверке: действительно ли
переданная длина — это длина данных? Это та же проверка, что и i + 1 < n.
long long sum = 0;int cnt = 0;for(int i = 0; i < n; i++){ sum += a[i]; // сумма до 10^5 чисел по 10^9: long long if(a[i]> k){ cnt++; // счётчик под if}}int mx = a[0], mn = a[0]; // начинаем с настоящего элемента, никогда не с 0for(int i = 1; i < n; i++){ mx = max(mx, a[i]); mn = min(mn, a[i]);}
проверь себя1 балл
a — это {3, 8, 1, 8, 2}. Что напечатает этот код?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Числа — 6 9 4 9. Программа находит индекс best первого максимума, а затем печатает наибольший из элементов на всех остальных индексах. Что она напечатает?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Вектор из n = 6 элементов циклически сдвигают вправо на k = 4 места с помощью b[(i + k) % n] = a[i]. На каком индексе b окажется a[3]?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
В векторе до 10⁵ чисел, каждое до 10⁹. Какой тип должен быть у переменной для их суммы?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Какой цикл сравнивает каждый элемент a[i] с его правым соседом a[i + 1] и ни разу не выходит за пределы вектора размера n?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
a — это {5, 8}. Что в нём будет после этих двух строк?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
7
12 30 7 30 25 30 1
30
2 4 6
10
0 3 5 0 0 2 7 1 4 0
4
7
10 20 30 40 50 60 70
3
50 60 70 10 20 30 40
int pos = -1;for(int i = 0; i < n; i++){ if(a[i] == x){ pos = i; break; // первое совпадение: дальше не ищем}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i];} int mx = a[0]; // проход 1: лучший результат for(int i = 1; i < n; i++){ mx = max(mx, a[i]);} cout << mx << "\n"; for(int i = 0; i < n; i++){ // проход 2: у кого он if(a[i] == mx){ cout << i + 1<< " "; // позиции считаются с 1}} cout << "\n"; return 0;}
bool sorted = true;for(int i = 0; i + 1< n; i++){ // последнее i — это n - 2: его сосед — a[n - 1] if(a[i]> a[i + 1]){ sorted = false;}}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i];} int run = 0, best = 0; // run: дождливых дней подряд до дня i for(int i = 0; i < n; i++){ if(a[i]> 0){ run++; // серия продолжается} else{ run = 0; // сухой день её прерывает} best = max(best, run);} cout << best << "\n"; return 0;}
bool pal = true;for(int i = 0; i < n / 2; i++){ if(a[i] != a[n - 1 - i]){ pal = false;}}
int last = a[n - 1];for(int i = n - 1; i > 0; i--){ a[i] = a[i - 1]; // справа налево}a[0] = last;
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i];} int k; cin >> k; vector<int> b(n); // новая рассадка for(int i = 0; i < n; i++){ b[(i + k) % n] = a[i]; // на k мест вправо, по кругу стола} for(int i = 0; i < n; i++){ cout << b[i]<< " ";} cout << "\n"; return 0;}
int best = 0;for(int i = 1; i < 5; i++){ if(a[i]>= a[best]){ best = i;}}cout << best + 1;