algoritmos STL

lower_bound e upper_bound são funções de busca binária incorporadas.

lower_bound - uma função que, em tempo logarítmico, encontra o menor elemento em uma matriz classificada que é maior ou igual ao valor dado k.
Toma os limites do array e o valor de k como argumentos.
Retorna um iterador para o elemento encontrado, ou para o final (não incluso) do array se tal elemento não existir.
Você pode ler mais na documentação.

upper_bound - uma função que em tempo logarítmico em uma matriz classificada encontra o menor elemento que é estritamente maior que o valor dado k.
Toma os limites do array e o valor de k como argumentos.
Retorna um iterador para o elemento encontrado, ou para o final (não incluso) do array se tal elemento não existir.
Você pode ler mais na documentação.

Vale esclarecer que o uso dessas funções em um conjunto ou multiconjunto não funciona em tempo logarítmico devido à falta de iteradores nas coleções de acesso aleatório acima.
No entanto, essas coleções têm métodos integrados correspondentes (ou seja, você precisa usá-los "através de um ponto").

Exemplos:
  vetor a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = lower_bound(a.begin(), a.end(), 4); // *isso == 5 it = lower_bound(a.begin(), a.end(), 5); // *isso == 5 it = lower_bound(a.begin(), a.end(), 8); // é == a.end() it = upper_bound(a.begin(), a.end(), 4); // *isso == 5 it = upper_bound(a.begin(), a.end(), 5); // *isso == 7 it = upper_bound(a.begin(), a.end(), -1); // *isso == 0 // subtraindo iteradores, você pode obter o índice do elemento encontrado int ind = lower_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // precisa usar métodos em vez de funções para conjuntos e coleções semelhantes set s{ 1, 3, 5 }; set::iterator sit; sentar = s.lower_bound(3); // *senta == 3 senta = s.upper_bound(3); // *senta == 5  

unique - uma função que comprime todas as sequências de elementos consecutivos idênticos em um em tempo linear.
Como argumento, são passados ​​os limites do array, dentro dos quais é necessário aplicar compressão.
Um iterador é retornado ao novo final (não incluso) da matriz. Você deve ter cuidado com os elementos após o novo fim, mas antes do antigo, pois eles terão um valor indefinido.
Você pode ler mais na documentação.

Se você estiver usando esta função em um vetor, é conveniente redimensionar usando o resultado retornado (mais sobre isso abaixo).

Exemplos:
  vetor a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; exclusivo(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // usando a função única é conveniente fazer // array auxiliar para compressão de coordenadas a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // a = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // a = [10, 41, 235, 500]  

merge - uma função que mescla dois arrays ordenados, ou seja, em tempo linear obtém um array ordenado, que consiste nos elementos do primeiro e do segundo array.
Leva 5 argumentos: dois limites para cada array e o limite esquerdo do destino (onde os elementos do array resultante serão colocados).
Mais detalhes podem ser encontrados na documentação.

Exemplos: // matrizes de origem devem ser classificadas vetor a = { 1, 3, 5, 7 }; vetor b = { 2, 4, 6 }; // precisa que o destino seja grande o suficiente vetor c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // os elementos podem ser repetidos a = {1, 2, 4, 4}; b = { 2, 3, 3, 3, 4, 4 }; c.resize(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Esta função é muito útil no contexto de classificação por mesclagem.

nth_element é uma função que permite encontrar o n-ésimo elemento em uma matriz em ordem de classificação em tempo linear.
A função pega a extremidade esquerda da matriz, um iterador para a posição cujo valor na ordem de classificação deve ser encontrado e a extremidade direita da matriz.
Após a aplicação da função, o valor necessário estará localizado no local indicado pelo iterador, enquanto os valores restantes adquirirão uma ordem caótica, mas à esquerda do enésimo haverá valores não mais que isso, e para a direita não menos. Ou seja, deve-se entender que esta função destrói a ordem original dos elementos.
Você pode ler mais na documentação (https://www.cplusplus.com/reference/algorithm/nth_element/).

Exemplo: vetor a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // procura elemento no índice 4 // presta atenção na ordem dos argumentos nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#, #, #, #, 4, $, $, $, $, $] // onde # <= 4 e 4 <= $  

Uma permutação de comprimento n é uma coleção ordenada sem repetições dos números 1, 2, ..., n. Por exemplo, [3, 1, 2] e [5, 4, 3, 2, 1] são permutações, mas [1, 2, 1, 3] e [1, 2, 4] não são.

Se a tarefa for reduzida ao fato de que é necessário iterar sobre todas as permutações de comprimento n, então você pode usar um mecanismo conveniente em C ++, chamado "next_permutation".

Você pode ler mais sobre isso em documentação, mas o ponto é que esta função altera o array passado à permutação subseqüente na ordem lexicográfica (que geralmente é clara e seu nome).

Para usar next_permutation, você precisa incluir a biblioteca de algoritmos (ou seja, escreva #include <algorithm> no início do programa)

Exemplos: vetor arr; arr = { 1, 2, 3 }; // matriz é [1, 2, 3] next_permutation(arr.begin(), arr.end()); // passa todo o array para a função // array agora é [1, 3, 2] arr = { 2, 3, 1 }; // matriz é [2, 3, 1] next_permutation(arr.begin(), arr.end()); // passa todo o array para a função // array agora é [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // é possível aplicar uma função a uma parte de um array, mas na prática isso raramente é necessário // array agora é [3, 2, 1]
Neste caso, a função tem um valor de retorno booleano que é true se a próxima permutação foi gerada e false se não houve próxima (caso em que a permutação máxima em ordem lexicográfica é passada para a função).
Isso torna possível usar a função em um loop, o que nos permitirá iterar todas as permutações de uma só vez. Devido à indexação 0, na prática muitas vezes é mais conveniente trabalhar com uma permutação de números de 0 a n - 1, embora uma permutação contenha formalmente números de 1 a n. Mas, felizmente, isso não leva a sobreposições adicionais no código, porque a função next_permutation é adaptada para permutações indexadas a 0 (e até elementos duplicados em uma matriz, mas você pode descobrir mais por conta própria).

Em geral, o código para iterar todas as permutações se parece com isto:   int; // tamanho da permutação vetorperm(n); // perm é a abreviação de "permutação", ou seja, "permutação" para (int i = 0; i < n; i++) perm[i] = i; // inicializa a permutação inicial 0, 1, ..., n - 1 fazer { // dentro do loop processamos a permutação atual } while (next_permutation(perm.begin(), perm.end())); // se não houver próxima permutação, então finalize o loop

Esse código é executado em O(n! * f(n)), onde f(n) é o tempo que você leva para processar uma permutação específica.