Em problemas de otimização combinatória, algumas abordagens gulosas se destacam por sua eficiência, como a troca adjacente e o guloso com regret (undoing greedy). Essas técnicas são aplicáveis quando a seleção de elementos envolve múltiplos critérios que influenciam a ordenação final ou a construção da solução.

1. Troca Adjacente (Adjacent Swap)

Esta técnica é baseada em uma ordenação seguida por comparações e trocas entre elementos adjacentes. O princípio fundamental é analisar como a escolha de dois itens, digamos a e b, afeta o custo. Se selecionar a antes de b gera um custo diferente de selecionar b antes de a, comparar esses custos determina a ordenação ótima.

A troca entre dois elementos adjacentes não altera o impacto sobre os demais elementos da sequência. Portanto, essa abordagem é válida apenas quando a influência mútua está restrita ao par em questão.

Exemplo: Problema dos Acrobatas (variante do Torneio de Pares)

Dados n acrobatas, cada um com peso w e força s. Eles devem ser empilhados. O risco de um acrobata i na base é o peso total dos acrobatas acima menos sua própria força. O objetivo é minimizar o risco máximo na pilha.

A abordagem gulosa ordena os acrobatas pelo critério w + s (ou uma expressão equivalente). O código abaixo implementa essa lógica:

#include <bits/stdc++.h>
using namespace std;

struct Acrobat {
    int weight;
    long long strength;
};

bool compareAcrobats(const Acrobat &a, const Acrobat &b) {
    return (a.weight + a.strength) < (b.weight + b.strength);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Acrobat> acrobats(n);
    for (int i = 0; i < n; ++i) {
        cin >> acrobats[i].weight >> acrobats[i].strength;
    }

    sort(acrobats.begin(), acrobats.end(), compareAcrobats);

    long long totalWeightAbove = 0;
    long long maxRisk = LLONG_MIN;

    for (const auto &acro : acrobats) {
        maxRisk = max(maxRisk, totalWeightAbove - acro.strength);
        totalWeightAbove += acro.weight;
    }

    cout << maxRisk << endl;
    return 0;
}

2. Guloso com Regret (Undoing Greedy)

Nesta técnica, as decisões tomadas não são finais. Durante o processo, as escolhes são armazenadas, geralmente em uma fila de prioridades. Se uma escolha atual se mostra inferior a uma anterior, uma operação de regret (desfazimento) ocorre: a escolha enterior é removida e substituída pela nova.

Essa abodragem é necessária quendo a seleção de um elemento afeta a viabilidade ou o custo de escolhas futuras. O desafio está em projetar a lógica de regret de forma correta.

Exemplo: Escalonamento de Trabalhos com Lucro Máximo

Dados n trabalhos, cada um com um prazo deadline e um valor profit. Cada trabalho consome uma unidade de tempo. O objetivo é maximizar o lucro total realizando trabalhos dentro de seus prazos.

A estratégia é:

1. Ordenar trabalhos por prazo.
2. Usar uma fila de prioridades mínima para manter os valores dos trabalhos já selecionados.
3. Se o trabalho atual couber no tempo disponível, adicioná-lo.
4. Senão, comparar seu valor com o menor valor já selecionado (topo da fila). Se for maior, fazer regret: remover o menor valor e adicionar o atual.

#include <bits/stdc++.h>
using namespace std;

struct Job {
    int deadline;
    int profit;
};

bool compareJobs(const Job &a, const Job &b) {
    return a.deadline < b.deadline;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Job> jobs(n);
    for (int i = 0; i < n; ++i) {
        cin >> jobs[i].deadline >> jobs[i].profit;
    }

    sort(jobs.begin(), jobs.end(), compareJobs);

    priority_queue<int, vector<int>, greater<int>> minHeap;
    long long totalProfit = 0;

    for (const auto &job : jobs) {
        if (job.deadline > minHeap.size()) {
            minHeap.push(job.profit);
            totalProfit += job.profit;
        } else {
            if (!minHeap.empty() && job.profit > minHeap.top()) {
                totalProfit += job.profit - minHeap.top();
                minHeap.pop();
                minHeap.push(job.profit);
            }
        }
    }

    cout << totalProfit << endl;
    return 0;
}

Observações

No guloso com regret, a decisão inicial é sempre incluir o elemento na estrutura de dados. A validação e o possível regret acontecem após essa inclusão, se necessário. Essa abordagem simplifica a lógica e é um padrão comum em problemas como agendamento de tarefas, seleção de projetos com restrições, entre outros.