Практика: Алгоритмы стандартной библиотеки

Одиннадцать задач на набор инструментов. Прежде чем писать цикл, спросите себя, какая функция уже это делает — и каким из них данные нужно сначала отсортировать.

• «Count Occurrences»: count по 10⁷ числам; читайте в vector<int>.
• «Extremes with Indices» и «Minimum and Position»: min_element и max_element дают позицию первого наименьшего и наибольшего — именно то, что просят обе задачи. Во второй значения достигают 10¹⁸.
• «All Maximum Positions»: *max_element для значения, затем один проход, чтобы собрать все индексы, где оно стоит.
• «Distinct Sorted Values»: sort, unique, erase, печать.
• «Frequency Table» и «Equal Coordinates»: отсортировать, затем пройти по сериям равных значений — или равных пар, которые сравниваются через ==, как и всё остальное.
• «Coordinate Compression»: отсортированные различные значения — это словарь; ранг a[i] равен lower_bound(v.begin(), v.end(), a[i]) - v.begin().
• «Funky Numbers»: выпишите треугольные числа до n (их около 45 000) и для каждого ищите через binary_search разность n и этого числа.
• «Anagram Groups»: свяжите каждое слово с его отсортированными буквами, {ключ, слово}; сортировка пар собирает каждую группу вместе, в алфавитном порядке внутри группы. Затем пройдите по сериям равных ключей.
• «Count Valid Triangles»: отсортируйте длины; для каждой пары i < j подходящие третьи стороны — это a[k] с k > j и a[k] < a[i] + a[j]; один lower_bound по части после j их считает. n ≤ 2000, так что n² поисков укладываются в лимит.