A tarefa consiste em selecionar um número específico de itens com custos e benefícios associados, sujeita a uma restrição de uso de vouchers. O objetivo é minimizar o custo total, garantindo que o número de vouchers utilizados não exceda um limite pré-definido.
Greedy com Reconsideração (Backtracking Greedy)
Uma abordagem gulosa direta, que prioriza o uso de vouchers nos itens de menor custo, pode falhar. Um exemplo clássico demonstra que essa estratégia não é ótima: ao comprar itens de baixo custo com vouchers, podemos perder a oportunidade de adquirir mais itens se os vouchers fossem aplicados de forma mais estratégica em itens com maior diferença entre o preço original e o preço com desconto.
A estratégia de reconsideração (ou "backtracking greedy") propõe uma solução mais robusta. Inicialmente, assume-se o uso de vouchers nos itens que oferecem o maior desconto. Para os itens restantes, onde os vouchers já foram esgotados, a decisão de compra é entre o preço original ou a substituição de um item anteriormente comprado com voucher. A substituição envolve o custo original do novo item mais o custo do item substituído com voucher, menos o preço de venda do item substituído.
Para implementar isso eficientemente, utilizamos três estruturas de dados (filas de prioridade): uma para os preços originais, outra para os custos com voucher e uma terceira para a diferença entre o preço original e o custo com voucher (representando o ganho potencial ao usar um voucher). As operações de inserção e remoção nessas estruturas permitem gerenciar as escolhas e substituições de forma dinâmica.
O processo iterativo envolve:
- Inicialmente, aplicar vouchers aos
kitens que resultam no menor custo total. - Para os itens subsequentes, comparar o custo de compra direta com a opção de substituir um item previamente adquirido com voucher. A substituição é vantajosa se o custo do novo item mais o ganho da substituição for menor que o custo de compra direta.
- Durante o processo, se o custo total exceder o orçamento
m, interrompe-se a seleção e retorna-se o número de itens adquiridos até aquele ponto.
A complexidade de tempo desta abordagem é de $O(N \log N)$, devido às operações nas filas de prioridade.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Item {
int price;
int voucher_cost;
int id;
// Para fila de prioridade de custo com voucher (min-heap)
bool operator>(const Item& other) const {
return voucher_cost > other.voucher_cost;
}
};
struct PriceDiff {
int diff;
int id;
// Para fila de prioridade de diferença de preço (min-heap)
bool operator>(const PriceDiff& other) const {
return diff > other.diff;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
ll k, budget;
cin >> n >> k >> budget;
vector<Item> items(n);
priority_queue<Item, vector<Item>, greater<Item>> voucher_pq; // Custos com voucher
priority_queue<PriceDiff, vector<PriceDiff>, greater<PriceDiff>> diff_pq; // Diferenças p[i] - c[i]
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> price_pq; // Preços originais
for (int i = 0; i < n; ++i) {
items[i].id = i;
cin >> items[i].price >> items[i].voucher_cost;
voucher_pq.push({items[i].price, items[i].voucher_cost, i});
price_pq.push({items[i].price, i});
diff_pq.push({items[i].price - items[i].voucher_cost, i});
}
ll current_cost = 0;
vector<int> item_status(n, 0); // 0: não comprado, 1: comprado sem voucher, 2: comprado com voucher
// Fase 1: Aplicar k vouchers aos itens de menor custo com voucher
for (int i = 0; i < k; ++i) {
Item best_voucher_item = voucher_pq.top();
voucher_pq.pop();
current_cost += best_voucher_item.voucher_cost;
item_status[best_voucher_item.id] = 2; // Marcado como comprado com voucher
diff_pq.push({items[best_voucher_item.id].price - items[best_voucher_item.id].voucher_cost, best_voucher_item.id}); // Adiciona a diferença para possível substituição
if (current_cost > budget) {
cout << i << endl;
return 0;
}
}
// Fase 2: Comprar os itens restantes
for (int i = k; i < n; ++i) {
// Limpar filas de prioridade de itens já comprados ou com status alterado
while (!price_pq.empty() && item_status[price_pq.top().second] != 0) {
price_pq.pop();
}
while (!voucher_pq.empty() && item_status[voucher_pq.top().id] != 0) {
voucher_pq.pop();
}
while (!diff_pq.empty() && item_status[diff_pq.top().id] != 2) { // Só consideramos diferenças de itens comprados com voucher
diff_pq.pop();
}
// Comparar compra direta vs. substituição de voucher
// Custo de compra direta: preço do item com menor preço original entre os não comprados
Item direct_buy_item = price_pq.top();
// Custo de substituição: Preço do item não comprado + diferença do item comprado com voucher
Item voucher_replace_item_candidate = voucher_pq.top(); // Menor custo com voucher entre os não comprados
PriceDiff best_diff_candidate = diff_pq.top(); // Maior ganho de substituição
// O "preço" da substituição é o custo do novo item (preço original) + o ganho (p[j] - c[j])
// Ou seja, custo_substituicao = p[novo] + (p[antigo] - c[antigo])
// A condição de compra é se p[novo] < c[novo] + (p[antigo] - c[antigo])
// Simplificando: p[novo] + c[antigo] < p[antigo] + c[novo] (comparando os custos totais)
// Opção 1: Comprar diretamente o item mais barato disponível
int cost_direct = price_pq.top().first;
// Opção 2: Substituir um item comprado com voucher
// O custo total se substituirmos é: custo_anterior - c[item_substituido] + p[novo_item]
// O "ganho" da substituição é: p[item_substituido] - c[item_substituido]
// Custo_substituicao = p[novo_item] + (p[item_substituido] - c[item_substituido])
// Para simplificar, comparamos o custo do novo item com o custo de substituição
// Se o item mais barato para comprar agora é mais caro que o custo de substituição otimizado
// Vamos usar os itens com menor preço para compra direta
Item item_to_buy_direct = price_pq.top();
// E o item que oferece a maior economia se substituído
PriceDiff potential_replacement = diff_pq.top();
Item replaced_item_info = items[potential_replacement.id]; // Informações do item a ser substituído
// Custo de comprar o item com menor preço direto
ll cost_if_direct_buy = item_to_buy_direct.first;
// Custo se fizermos a substituição:
// Custo = (custo_atual - custo_voucher_do_substituido) + preco_original_do_novo_item + diferenca_do_substituido
// Custo = custo_atual - items[potential_replacement.id].voucher_cost + item_to_buy_direct.first + potential_replacement.diff;
// Uma forma mais direta de pensar:
// Queremos escolher entre comprar 'item_to_buy_direct' diretamente
// OU substituir um item 'replaced_item_info' (que foi comprado com voucher) por 'item_to_buy_direct'.
// A substituição é vantajosa se o custo de 'item_to_buy_direct' for menor que
// o "custo efetivo" de manter o voucher no item substituído e comprar o novo item separadamente (se possível).
// Comparação: Custo de comprar item_to_buy_direct diretamente vs. custo de substituir um item com voucher por ele.
// Se custo_direto <= custo_substituicao_otimizado
// Custo_substituicao_otimizado = p[novo] + (p[antigo] - c[antigo])
// Vamos comparar o preço do item mais barato não comprado (item_to_buy_direct)
// com o "custo de não usar o voucher mais vantajoso agora".
// Se o preço do item mais barato não comprado for menor ou igual ao
// preço do item com voucher + a diferença que perderíamos (p[substituido] - c[substituido]),
// então é melhor comprar diretamente.
// Melhor item para substituição (maior diferença p[i]-c[i])
PriceDiff best_diff_to_replace = diff_pq.top();
// Item mais barato para compra direta
Item cheapest_direct_buy = price_pq.top();
// Custo se comprarmos o item mais barato diretamente: cheapest_direct_buy.first
// Custo se fizermos a substituição:
// Precisamos do custo original do item mais barato que NÃO foi comprado com voucher.
// E o item que tem o maior p[i] - c[i] entre os comprados com voucher.
// A lógica correta é: se o item mais barato que ainda não foi comprado
// tem um custo (preço original) menor que o custo que teríamos se o
// comprássemos com um voucher + o ganho que perderíamos ao não usar
// o voucher de forma ótima, então compramos diretamente.
// Custo de compra direta: cheapest_direct_buy.first
// Custo de "não usar o voucher de forma ótima":
// O item com o maior ganho (p[i] - c[i]) entre os comprados com voucher é best_diff_to_replace.id
// O custo que estamos comparando é:
// items[best_diff_to_replace.id].voucher_cost + cheapest_direct_buy.first
// Se cheapest_direct_buy.first <= items[best_diff_to_replace.id].voucher_cost + best_diff_to_replace.diff
// Ou seja, se o custo direto for menor ou igual ao custo de comprar o novo item E
// manter o voucher no item antigo (o que é implícito na diferença).
// A comparação simplificada:
// Se o item mais barato disponível (preço original) for MAIOR que
// o custo do item com voucher + a diferença econômica do melhor voucher a ser substituído
// então compramos o item mais barato diretamente.
// Caso contrário, realizamos a substituição.
// Reavaliando a lógica:
// Queremos comprar o item mais barato disponível (price_pq.top()) ou
// substituir um item que usamos voucher (diff_pq.top()) por este item mais barato.
// A substituição é vantajosa se:
// Custo_novo_item_comprado_direto > Custo_novo_item_com_voucher_antigo + Ganho_substituição
// Ou seja, se preço_direto > voucher_cost_antigo + (price_antigo - voucher_cost_antigo)
// Isso se simplifica para: preço_direto > preço_antigo - voucher_cost_antigo + voucher_cost_antigo
// Isso não está certo. A comparação correta é:
// Comprar diretamente o item mais barato (cheapest_direct_buy.first)
// versus
// O custo de usar o melhor voucher disponível (voucher_pq.top().voucher_cost) +
// o custo do item mais barato que ainda não foi comprado (cheapest_direct_buy.first)
// MENOS o ganho que teríamos se usássemos o melhor voucher (best_diff_to_replace.diff)
// A lógica que funciona é comparar o preço do item mais barato disponível
// com o custo de usarmos o voucher que nos dá mais economia.
// Se o preço do item mais barato é MENOR que o custo do item com voucher + a diferença que ele nos dá,
// então é melhor comprar o item mais barato diretamente.
// Se cheapest_direct_buy.first <= voucher_pq.top().voucher_cost + best_diff_to_replace.diff
// Então compramos o item mais barato diretamente.
// senão, fazemos a substituição.
// A formulação mais simples e correta é:
// Comparar:
// 1. Comprar o item mais barato não comprado (cheapest_direct_buy.first)
// 2. Substituir o item com melhor ganho (best_diff_to_replace.id) com o item mais barato não comprado.
// O custo da substituição é:
// Custo_atual - voucher_cost_do_substituido + preco_original_do_novo_item + ganho_da_substituicao
// Custo_atual - items[best_diff_to_replace.id].voucher_cost + cheapest_direct_buy.first + best_diff_to_replace.diff
// Para evitar recalcular custo_atual, comparamos os custos incrementais:
// Custo de comprar diretamente: cheapest_direct_buy.first
// Custo de substituição otimizada:
// Precisamos do item mais barato que NÃO foi comprado COM voucher.
// E o item com maior diferença (p[i] - c[i]) entre os comprados COM voucher.
// Se o item mais barato (preço original) é MAIOR que o item com voucher
// mais a diferença de preço desse item, então é melhor comprar o item mais barato diretamente.
// Ou seja, se price_pq.top().first >= voucher_pq.top().voucher_cost + diff_pq.top().diff
// A compra direta é mais vantajosa.
// Se o item mais barato (p[i]) for mais caro que a combinação
// do item com menor custo com voucher (c[j]) + a diferença do item
// que tem o maior p[i]-c[i] (diff_pq.top().diff),
// então é melhor comprar o item mais barato diretamente.
// A condição de substituição é:
// price_pq.top().first > voucher_pq.top().voucher_cost + diff_pq.top().diff
// Se essa condição for VERDADEIRA, compramos diretamente.
// Se for FALSA, realizamos a substituição.
// Let's use the elements directly:
Item item_to_buy_direct_candidate = price_pq.top();
PriceDiff best_replacement_candidate = diff_pq.top();
// Custo se comprarmos diretamente: item_to_buy_direct_candidate.first
// Custo se fizermos a substituição:
// Precisamos do custo do item que será substituído (que foi comprado com voucher)
// E o custo original do novo item.
// O ganho da substituição é best_replacement_candidate.diff
// O custo original do item que será substituído é items[best_replacement_candidate.id].price
// O custo com voucher do item que será substituído é items[best_replacement_candidate.id].voucher_cost
// Se o item mais barato disponível (p[i]) é menor ou igual a
// o custo com voucher do item que estamos substituindo (c[j]) mais
// a economia que obteríamos com a substituição (p[j] - c[j]),
// então é mais vantajoso comprar o item mais barato diretamente.
// cheapest_direct_buy.first <= items[best_replacement_candidate.id].voucher_cost + best_replacement_candidate.diff
if (item_to_buy_direct_candidate.first <= items[best_replacement_candidate.id].voucher_cost + best_replacement_candidate.diff) {
// Comprar diretamente o item mais barato
current_cost += item_to_buy_direct_candidate.first;
item_status[item_to_buy_direct_candidate.second] = 1; // Comprado sem voucher
price_pq.pop();
} else {
// Realizar a substituição
// Custo anterior - custo voucher do substituído + preço original do novo + diferença
current_cost = current_cost - items[best_replacement_candidate.id].voucher_cost + item_to_buy_direct_candidate.first + best_replacement_candidate.diff;
item_status[best_replacement_candidate.id] = 1; // O item substituído agora é comprado sem voucher (ou não comprado, dependendo do fluxo)
item_status[item_to_buy_direct_candidate.second] = 2; // O novo item é comprado com voucher (substituído)
// Atualizar as filas de prioridade
price_pq.pop(); // Remove o item comprado
diff_pq.pop(); // Remove o item substituído da fila de diferenças
voucher_pq.push({items[best_replacement_candidate.id].price, items[best_replacement_candidate.id].voucher_cost, best_replacement_candidate.id}); // Reinsere o item substituído na fila de custos com voucher
diff_pq.push({items[item_to_buy_direct_candidate.second].price - items[item_to_buy_direct_candidate.second].voucher_cost, item_to_buy_direct_candidate.second}); // Adiciona a diferença do novo item comprado com voucher
}
if (current_cost > budget) {
cout << i << endl;
return 0;
}
}
cout << n << endl;
return 0;
}
Bisseção de WQS Acoplada com Bisseção
Uma alternativa mais robusta é empregar a técnica de bisseção de WQS (Wang-Qian-Shieh-Shieh) combinada com bisseção. Essa abordagem transforma o problema em uma série de subproblemas verificáveis. A questão central se torna: qual o custo mínimo para adquirir exatamenet x itens, utilizando estritamente k vouchers?
A função check(x) verifica se é possível adquirir x itens com um custo total inferior ou igual ao budget, utilizando no máximo k vouchers. Esta verificação pode ser otimizada para tempo linear $O(N)$ utilizando uma estratégia gulosa, que explora as diferenças de custo e a disponibilidade de vouchers.
A bisseção de WQS introduz um parâmetro lambda (representado por mid na função check1) que penaliza o uso de vouchers. Ao ajustar lambda, o problema original é decomposto em subproblemas onde a escolha entre comprar com voucher ou sem voucher é simplificada. A função check1(lambda, n) calcula o custo mínimo para adquirir n itens, considerando a penalidade lambda por voucher. Ela opera em tempo $O(N)$.
A bisseção principal (em main) busca o número máximo de itens (mid) que podem ser adquiridos dentro do orçamento. Para cada mid, chamamos a função check(mid), que por sua vez realiza a bisseção de WQS (check1). A complexidade total é $O(N \log N \log V_{max})$, onde $V_{max}$ é o valor máximo do parâmetro lambda. Essa abordagem é viável e geralmente mais estável que a abordagem gulosa pura.
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Item {
int price;
int voucher_cost;
int id;
// Para ordenação por preço original
bool operator<(const Item& other) const {
return price < other.price;
}
};
struct VoucherItem {
int cost;
int id;
// Para ordenação por custo com voucher (min-heap)
bool operator>(const VoucherItem& other) const {
return cost > other.cost;
}
};
int n;
ll k, budget;
ll current_total_cost;
int items_count;
vector<Item> items_by_price;
vector<Item> items_by_voucher_cost;
vector<bool> used_voucher_on;
// Função para verificar a viabilidade de comprar 'count' itens com um dado 'voucher_penalty'
void check_feasibility(int count, int voucher_penalty) {
current_total_cost = 0;
items_count = 0;
used_voucher_on.assign(n, false);
priority_queue<VoucherItem, vector<VoucherItem>, greater<VoucherItem>> available_vouchers; // Itens comprados com voucher
int price_idx = 0;
int voucher_cost_idx = 0;
// Iterar para decidir a compra de cada item
// Para cada item, escolhemos a opção mais barata: comprar com preço original
// ou usar um voucher (custo + penalidade).
// Precisamos manter controle dos itens comprados com voucher para poder "descartá-los" se o preço original for melhor.
// Ordenar os itens por preço original e custo com voucher
sort(items_by_price.begin(), items_by_price.end());
sort(items_by_voucher_cost.begin(), items_by_voucher_cost.end(), [](const Item& a, const Item& b) {
return a.voucher_cost < b.voucher_cost;
});
// Estratégia: Iterar pelos itens em ordem de preço original.
// Para cada item, decidir se é melhor comprá-lo com preço original ou com voucher.
// Se o preço original for menor que o custo com voucher + penalidade, compramos com preço original.
// Caso contrário, usamos um voucher se tivermos disponíveis.
// Vamos usar uma abordagem diferente:
// Para `count` itens, precisamos escolher quais comprar.
// A função `check_feasibility` calcula o custo mínimo para comprar `count` itens.
// Vamos iterar por todos os `n` itens e decidir se os incluímos na compra dos `count` itens.
// Vamos reestruturar:
// A função `check_feasibility` deve retornar o custo mínimo para comprar `count` itens.
// Para fazer isso, precisamos considerar o uso de vouchers.
// Nova abordagem para check_feasibility:
// Considerar cada item. A decisão de compra é entre:
// 1. Preço original: p[i]
// 2. Custo com voucher: c[i] + voucher_penalty
// Se p[i] < c[i] + voucher_penalty, é melhor comprar com preço original.
// Se p[i] >= c[i] + voucher_penalty, é melhor usar um voucher (se disponível).
// Vamos contar quantos itens são comprados com preço original e quantos com voucher.
vector<pair<int, int>> choices; // pair<cost, id>
int vouchers_used = 0;
for (int i = 0; i < n; ++i) {
int direct_cost = items_by_price[i].price;
int voucher_option_cost = items_by_voucher_cost[i].voucher_cost + voucher_penalty;
// Precisamos garantir que não usemos o mesmo item duas vezes.
// E que escolhamos os `count` itens mais baratos.
// Melhor estratégia: Para cada item, calcular seu custo efetivo considerando a penalidade.
// O custo efetivo é min(p[i], c[i] + voucher_penalty).
// Precisamos escolher os `count` itens com os menores custos efetivos.
// E então verificar se o número de vouchers usados não excede k.
// Isso requer uma maneira de associar o custo efetivo ao item correto e ao uso do voucher.
// Vamos simplificar a lógica de `check_feasibility`.
// Queremos comprar `count` itens. Para cada item, ele pode ser comprado:
// 1. Com preço original: p[i]
// 2. Com voucher: c[i]
// A penalidade `voucher_penalty` é adicionada ao custo do voucher.
// Queremos minimizar o custo total, usando no máximo `k` vouchers.
// Precisamos escolher `count` itens. Para cada item `i`:
// Custo A: p[i]
// Custo B: c[i] + voucher_penalty
// Se A < B, o custo efetivo é A. Se usarmos B, um voucher é consumido.
// Se A >= B, o custo efetivo é B. Um voucher é consumido.
// Iterar pelos itens em ordem de preço original é uma boa heurística.
// Para cada item `i` (ordenado por preço original):
// Se `items_by_price[i].price < items_by_voucher_cost[i].voucher_cost + voucher_penalty`:
// O custo efetivo é `items_by_price[i].price`. Compramos diretamente.
// Else:
// O custo efetivo é `items_by_voucher_cost[i].voucher_cost + voucher_penalty`.
// Se tivermos vouchers disponíveis (`vouchers_used < k`), usamos um.
// Senão, somos forçados a comprar pelo preço original.
// Esta lógica ainda é complexa pois a ordenação por preço original não garante a escolha ótima com vouchers.
// Abordagem correta para `check_feasibility(count, voucher_penalty)`:
// Queremos selecionar `count` itens.
// Para cada item `i`, temos duas opções de custo:
// Opção 1: custo `p[i]` (sem usar voucher)
// Opção 2: custo `c[i] + voucher_penalty` (usando voucher)
// Precisamos escolher `count` itens para minimizar o custo total.
// A escolha de `count` itens depende de seus custos efetivos.
// O custo efetivo de um item `i` é `min(p[i], c[i] + voucher_penalty)`.
// No entanto, se escolhermos `c[i] + voucher_penalty`, um voucher é consumido.
// Vamos calcular os custos efetivos para todos os itens:
vector<pair<int, int>> effective_costs; // pair<cost, voucher_used_flag>
for(int i=0; i<n; ++i) {
int direct_p = items_by_price[i].price;
int voucher_c_penalty = items_by_voucher_cost[i].voucher_cost + voucher_penalty;
if (direct_p < voucher_c_penalty) {
effective_costs.push_back({direct_p, 0}); // 0 indicates no voucher used
} else {
effective_costs.push_back({voucher_c_penalty, 1}); // 1 indicates voucher used
}
}
// Ordenar os custos efetivos
sort(effective_costs.begin(), effective_costs.end());
// Somar os `count` menores custos efetivos
ll min_cost_for_count = 0;
int vouchers_needed = 0;
for (int i = 0; i < count; ++i) {
min_cost_for_count += effective_costs[i].first;
vouchers_needed += effective_costs[i].second;
}
current_total_cost = min_cost_for_count;
items_count = vouchers_needed; // Number of vouchers needed for these 'count' items
}
// `check` function: determines if `count` items can be bought within budget `m`
// using at most `k` vouchers.
bool check(int count) {
// Binary search for the minimum voucher penalty (`lambda`)
int low_penalty = -1e9 - 7, high_penalty = 0; // Penalty can be negative
int best_penalty = 0;
while (low_penalty < high_penalty) {
int mid_penalty = low_penalty + (high_penalty - low_penalty) / 2;
check_feasibility(count, mid_penalty);
// If we used `k` or fewer vouchers, it means the penalty might be too high,
// or just right. We can try a lower penalty.
if (items_count >= k) {
high_penalty = mid_penalty - 1;
} else { // Used less than k vouchers, penalty might be too low.
best_penalty = mid_penalty; // Store this as a potential best penalty
low_penalty = mid_penalty + 1;
}
}
// After binary search, `low_penalty` (or `best_penalty`) is the minimum penalty
// for which we can buy `count` items using at most `k` vouchers.
// Recalculate with the best penalty found.
check_feasibility(count, low_penalty); // Using low_penalty which is the final result of BS
// Check if the total cost with the best penalty is within budget.
return current_total_cost <= budget;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k >> budget;
items_by_price.resize(n);
items_by_voucher_cost.resize(n);
for (int i = 0; i < n; ++i) {
items_by_price[i].id = i;
items_by_voucher_cost[i].id = i;
cin >> items_by_price[i].price >> items_by_voucher_cost[i].voucher_cost;
}
// Binary search for the maximum number of items (`count`) we can buy.
int max_items_possible = 0;
int low_count = 0, high_count = n;
while (low_count <= high_count) {
int mid_count = low_count + (high_count - low_count) / 2;
if (mid_count == 0) { // Always possible to buy 0 items
max_items_possible = max(max_items_possible, mid_count);
low_count = mid_count + 1;
continue;
}
if (check(mid_count)) {
max_items_possible = max(max_items_possible, mid_count);
low_count = mid_count + 1; // Try to buy more items
} else {
high_count = mid_count - 1; // Cannot afford `mid_count` items, try fewer
}
}
cout << max_items_possible << endl;
return 0;
}