На самом деле я считаю, что сортировка подсчетом самая простая и самая нужная сортировка, которую нужно знать, например я находил решения довольно сложных для меня задач именно при помощи сортировки подсчетом, могу привести пример:
Задачу 1546C - AquaMoon and Strange Sort я например решил при помощи сортировки подсчетом, так как у неё были маленькие ограничения по числам на футболках (всего до 1e5), я решил создать два массива, где учитывал четные и нечетные индексы массива, а потом пробегался уже по отсортированному масиву и вычитал 1, если индекс стоит на четной позиции из массива с четными номерами (то есть even[a[i]] -= 1) и то же самое делала с нечетными индексами.
Итог:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline string solve(vector<int> &odd, vector<int> &even, vector<int> a, int n){
for (int i = 0; i < n; ++i) {
if (even[a[i]] != 0){
if (i % 2 == 0){
even[a[i]]--;
}
}
if (odd[a[i]] != 0){
if (i % 2 != 0){
odd[a[i]]--;
}
}
}
for (int i = 0; i < n; ++i) {
if (even[a[i]] != 0 || odd[a[i]] != 0){
return "NO";
}
}
return "YES";
}
signed main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vector<int> odd(1e5 + 1, 0), even(1e5 + 1, 0);
for (int i = 0; i < n; ++i) {
if (i % 2 == 0){
even[a[i]] += 1;
}else{
odd[a[i]] += 1;
}
}
sort(a.begin(), a.end());
cout << solve(odd, even, a, n) << "\n";
}
return 0;
}
Мне бы очень хотелось узнать какие алгоритмы вы считаете незаменимыми и чаще всего используете ;)