Мультимножества и Обработка данных по ключу - Язык программирования C++ для спортивного программирования
Неделя 11Множества, Словари, Мультимножества и Обработка данных по ключу
Мультимножества и Обработка данных по ключу
Мультимножество хранит повторы: удаление одной копии или всех, мультимножество или словарь счётчиков, записи, сгруппированные по ключу, итог для каждого ключа, где значение встречалось в последний раз, обход ключей в обратном порядке и выбор контейнера.
Теория
Урок 5 из 7
36 мин чтения
Вопросов: 6
Множество выбрасывает повторы. Но иногда повторы — это и есть данные: два
игрока с одинаковым счётом, три макаронины одной длины, одна и та же цена у двух
товаров. Мультимножество (multiset) хранит все копии — и держит их по
порядку. А когда данные лежат в множествах и словарях, большинство задач о
записях — именах, номерах, датах, баллах — сводится к одному вопросу: что
здесь ключ?
Множество, которое хранит повторы
multiset объявляют и заполняют так же, как множество:
Программа печатает
У multiset те же операции, что у set, только копии разрешены:
insert(x) всегда добавляет копию, а size() считает каждую копию: 6.
count(x) — сколько копий x: три семёрки.
Обход посещает каждую копию от меньшей к большей. *ms.begin() — наименьшее
значение, *ms.rbegin() — наибольшее; lower_bound и upper_bound работают
так же, как в множестве.
Удаление одной копии
Две последние строки этой программы — главная ловушка урока:
ms.erase(x) удаляет все копии x;
ms.erase(ms.find(x)) удаляет одну копию: find указывает на одну
копию, а удаление позиции убирает только её.
Если x нет, find возвращает ms.end(), а удаление end() ломает
программу — часто она просто падает. Поэтому сначала проверьте, если только
задача не обещает, что x есть:
Потренируйтесь различать: каждый мешок должен стать точно таким, как цель, а
ходов ровно столько, сколько в самом коротком решении.
{3, 3, 7, 7, 7, 10} можно хранить и как словарь, где каждому значению
сопоставлено число его копий: {3: 2, 7: 3, 10: 1}. Информация одна и та же,
так что вопрос в том, что с ней нужно делать:
Нужно…
Берите
наименьшее или наибольшее значение, lower_bound, все копии по порядку
multiset
много раз узнавать, сколько копий x
map<value, int>
добавлять или удалять одну копию
любой: insert / erase(find(x)) или cnt[x]++ / cnt[x]--
Вторая строка важна: ms.count(x) проходит по каждой копии x, поэтому при
100 000 копий один вызов count — это 100 000 шагов. cnt[x] занимает около
log₂ n, сколько бы копий ни было.
multiset<string> хранит слова вместе с повторами в словарном порядке:
вставьте их все и обойдите мультимножество — они напечатаются отсортированными.
Записи, сгруппированные по ключу
Значением в словаре может быть что угодно — даже вектор. Тогда каждый ключ
собирает свой собственный список — это и нужно в такой задаче:
В первой строке n, во второй — n целых чисел на позициях от 1 до n.
Для каждого различного значения по возрастанию выведите позиции, на которых
оно встречается.
Для 4 9 4 4 2 9 7 программа печатает
where[x] — пустой вектор, когда x встречается впервые, а push_back
добавляет позиции по порядку. Значит, в k-й раз x встречается на позиции
where[x][k - 1] — но сначала проверьте, что x есть среди ключей и что
where[x].size() >= k.
Так можно сгруппировать любые записи по любому ключу: оценки ученика — под его
именем, города — под своей страной, коробки — под картой, которая в них лежит.
Внутренним контейнером может быть также set или multiset, когда каждая группа
должна быть отсортирована или храниться без повторов.
Итог для каждого ключа
Часто нужна не вся группа, а только её итог: сумма, максимум, сколько раз
максимум был достигнут. Например:
Каждый результат — это название команды и её баллы. Для каждой команды в
алфавитном порядке выведите её лучший результат и сколько раз команда его
показала.
Заведите по словарю на каждое нужное число — здесь best и times — и
обновляйте значения команды, когда приходит очередной результат:
Итог для каждого ключа: лучший результат и сколько раз он встретился
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<string> team = {"owls", "cats", "owls", "cats", "owls"};
9 vector<int> score = {70, 50, 90, 50, 90};
10 map<string, int> best, times;
11 for (int i = 0; i < 5; i++) {
12 string t = team[i];
13 if (!best.count(t) || score[i] > best[t]) {
14 best[t] = score[i]; // новый лучший, пока встретился один раз
Проверка !best.count(t) || score[i] > best[t] — это «первый раз или лучше
лучшего на данный момент», записанное через ключи. || сначала проверяет левую часть, поэтому
для команды, которой ещё нет, best[t] не читается — и не добавляется.
Где я видел его в последний раз?
Словарь, где для каждого значения хранится его позиция, отвечает на
вопросы о времени: когда этот посетитель приходил в последний раз, как давно
играла эта песня?
Каждый день, в дни от 0 до n - 1, приходит один посетитель; во вводе — n
и затем номер посетителя каждого дня. В первой строке для каждого дня
выведите, сколько дней прошло с прошлого визита этого посетителя, или -,
если он пришёл впервые. Во второй строке для каждого дня выведите, сколько
различных посетителей пришло к этому дню.
Для посетителей 12 5 12 7 5 12 9 программа печатает
Словарь хранит только последний день, а last[id[i]] = i стоит после
вопроса, поэтому старый день читается до того, как его заменят. Для второй
строки словарь вообще не нужен: это размер множества после каждой вставки.
Самый длинный отрезок без повторов
Последняя позиция решает и такую задачу:
Дан массив. Найдите длину самого длинного отрезка подряд идущих значений, в
котором ни одно значение не встречается дважды.
Пусть отрезок — это a[start..i]. Если a[i] в последний раз встречалось
внутри него, отрезок должен начинаться сразу после той, прежней копии:
Где его видели в последний раз? Самый длинный отрезок без повторов
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, 5, 8, 2, 3, 6};
9 map<int, int> last; // значение -> его последняя позиция
10 int start = 0, best = 0; // в a[start..i] нет повторов
Найдём самый длинный отрезок подряд идущих значений, в котором ни одно значение не повторяется.
a7 ячеек
3
8
5
8
2
3
6
0
1
2
3
4
5
6
map<int, int> lastСловарь
пусто
start—best—i—
нажми пуск
1 / 34
Обратите внимание на проверку last[a[i]] >= start: вторая тройка уже
встречалась, но на позиции 0, вне текущего отрезка, — поэтому она ничему не
мешает.
По ключу в обе стороны
Обход словаря уже отсортирован по ключу. Чтобы идти от наибольшего ключа
вниз, обходите словарь задом наперёд: rbegin() — последний элемент, а
rend() — позиция перед первым. На таких обратных позициях it++ шагает к
началу:
Так можно, когда у каждой записи свой ключ. Если у двух записей ключ может
совпасть — два ученика с одинаковым баллом, — map<int, string> сохранит
только одного из них: возьмите map<int, vector<string>> или отсортируйте
вектор пар, как на неделе 8.
Какой контейнер?
Контейнер
Хранит
Берите, когда
vector<T>
значения подряд, по индексу
важен порядок и нужен доступ по позиции
set<T>
различные значения по порядку
«видел ли я это?», «сколько различных?», ближайшее значение
multiset<T>
значения с повторами по порядку
наименьшее или наибольшее в меняющемся наборе, удаление одной копии
map<K, V>
значение для каждого ключа, по порядку ключей
подсчёт, группировка, итоги и поиск по ключу
Выберите для нескольких настоящих задач:
Какой контейнер?попробуй!
Проверьте себя
3 3 7 7 7 10
6 3
3 10
5 2
3 0
А вы знали?
Идея старая, а слово молодое: по словам Дональда Кнута, название multiset
(«мультимножество») предложил нидерландский математик Николас де Брёйн в
1970-х годах. У того же понятия есть и другое имя — мешок (bag): в мешок
можно положить два одинаковых шарика, а в множество нельзя.
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); multiset<int> ms ={7, 3, 7, 10, 7, 3}; for(int x : ms){ // каждая копия, от меньшего к большему cout << x << " ";} cout << "\n"; cout << ms.size()<< " "<< ms.count(7)<< "\n"; cout << *ms.begin()<< " "<< *ms.rbegin()<< "\n"; // наименьшее и наибольшее ms.erase(ms.find(7)); // удаляет ОДНУ копию 7 cout << ms.size()<< " "<< ms.count(7)<< "\n"; ms.erase(3); // удаляет ВСЕ копии 3 cout << ms.size()<< " "<< ms.count(3)<< "\n"; return 0;}
auto it = ms.find(x);if(it != ms.end()){ ms.erase(it); // одной копии x больше нет}
проверь себя1 балл
multiset<int> ms = {4, 4, 1, 4};, затем ms.insert(1);. Чему равно ms.size()?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Если в мультимножестве 100 000 копий x, ms.count(x) выполняется примерно за 17 шагов.
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает программа?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Какова длина самого длинного отрезка подряд идущих значений без повторов в 4 2 4 3 2 5?
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Что напечатает программа?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
проверь себя1 балл
Люди встают в очередь и уходят из неё. После каждого изменения нужен рост самого высокого, и у двух людей может быть одинаковый рост. Какой контейнер подходит лучше всего?
Выберите один ответ
Войдите, чтобы ответить и сохранить прогресс.Войти
2: 5
4: 1 3 4
7: 7
9: 2 6
- - 2 - 3 3 -
1 2 2 3 3 3 4
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; map<int, vector<int>> where; // значение -> все позиции, где оно встречается for(int i = 1; i <= n; i++){ int x; cin >> x; where[x].push_back(i); // новый ключ начинается с пустого вектора} for(auto p : where){ cout << p.first<< ":"; for(int i : p.second){ cout << " "<< i;} cout << "\n";} return 0;}
#include <bits/stdc++.h>using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector<int> id(n); for(int i = 0; i < n; i++){ cin >> id[i];} map<int, int> last; // посетитель -> день его последнего визита for(int i = 0; i < n; i++){ if(last.count(id[i])){ cout << i - last[id[i]]<< " "; // сколько дней прошло с прошлого визита} else{ cout << "- "; // первый визит} last[id[i]] = i;} cout << "\n"; set<int> seen; for(int i = 0; i < n; i++){ seen.insert(id[i]); cout << seen.size()<< " "; // различных посетителей за дни 0..i} cout << "\n"; return 0;}
for(auto it = m.rbegin(); it != m.rend(); it++){ cout << it->first<< " "<< it->second<< "\n";}
vector<int> a ={3, 1, 3, 3, 2, 1};map<int, vector<int>> where;for(int i = 0; i < 6; i++){ where[a[i]].push_back(i);}cout << where[3][1];