Purchasing Milk

Explicación

Primero, preprocesamos el arreglo de costos de modo que $a_i$ sea el costo mínimo para comprar $2^i$ baldes. Esto se logra asignando a $a_i$ el valor $\min(a_i, 2 \cdot a_{i-1})$ al recorrer $i$ de menor a mayor, porque podemos usar la oferta original o usar dos de las ofertas anteriores. Solo hace falta conservar las primeras $30$ potencias porque $x \le 10^9$ y $2^{30} \gt 10^9$ . Completamos cualquiera de los treinta elementos restantes si hace falta.

Luego procedemos de forma voraz. Supongamos que actualmente nos faltan $x$ baldes de leche. Podemos comprar la oferta de mayor potencia de dos que no exceda $x$ , que corresponde al costo en el índice $\lfloor\log_{2}\left(x\right)\rfloor$ . No es óptimo comprar una cantidad que sea una potencia de dos más chica. La segunda opción es pasarse de $x$ , lo que corresponde al costo en el índice $\lceil\log_{2}\left(x\right)\rceil$ . No es óptimo pasarse con una potencia de dos mayor porque los costos son más altos en índices más altos. Un ejemplo en el que es óptimo pasarse es $x = 7$ y $a=[10,20,40,60]$ . Se puede obtener un costo de $70$ moonies comprando exactamente $7$ baldes de leche, pero se puede lograr un costo menor de $60$ moonies comprando de inmediato $8$ baldes de leche.

Implementación

Complejidad temporal: $\mathcal{O}(N + Q)$

C++Python


#include <climits>
#include <cmath>
#include <iostream>
#include <vector>
 
const int BITS = 30;
 
int main() {
	int n, q;
	std::cin >> n >> q;
	std::vector<long long> costs(n);
 
	for (long long &x : costs) { std::cin >> x; }
 
	// precompute minimum costs for power of 2 bucket amounts
	for (int i = 1; i < BITS; i++) {
		if (i >= n) {
			costs.push_back(2LL * costs[i - 1]);
		} else {
			costs[i] = std::min(costs[i], 2LL * costs[i - 1]);
		}
	}
 
	while (q--) {
		long x;
		std::cin >> x;
		long long curr_cost = 0;
		long long answer = LLONG_MAX;
 
		while (x > 0) {
			long largest_idx = floor(std::log2(x));
			long overshoot_idx = ceil(std::log2(x));
			// overshoot
			answer = std::min(answer, curr_cost + costs[overshoot_idx]);
			// buy largest power of 2 that doesn't overshoot
			curr_cost += costs[largest_idx];
			x -= 1LL << largest_idx;
		}
		// never overshoot
		answer = std::min(answer, curr_cost);
		std::cout << answer << '\n';
	}
}


import math
 
n, q = map(int, input().split())
costs = [int(x) for x in input().split()][:30]
 
# precompute minimum costs for power of 2 bucket amounts
for i in range(1, 30):
	if i >= n:
		costs.append(2 * costs[i - 1])
	else:
		costs[i] = min(costs[i], 2 * costs[i - 1])
 
for i in range(q):
	x = int(input())
	curr_cost = 0
	answer = float("inf")
 
	while x > 0:
		largest_idx = math.floor(math.log2(x))
		overshoot_idx = math.ceil(math.log2(x))
		# overshoot
		answer = min(answer, curr_cost + costs[overshoot_idx])
		# buy largest power of 2 that doesn't overshoot
		curr_cost += costs[largest_idx]
		x -= 2**largest_idx
	# never overshoot
	answer = min(answer, curr_cost)
	print(answer)