Rental Service

Pista 1

¿Hay alguna razón para que Farmer John ordeñe una vaca que produce menos leche en vez de una que produce más? En la misma línea, ¿hay alguna razón para que alquile una vaca que produce más leche en vez de una que produce menos?

Respuesta a la pista 1

¡No la hay! Siempre es óptimo ordeñar la vaca que produce más leche o alquilar la vaca que produce menos leche.

Solución

Análisis oficial (Java)

Explicación

Notemos que siempre debemos comparar la vaca de mayor producción y la tienda que ofrece más dinero con el granjero que ofrece más dinero.

Para esto, podemos hacer 3 listas con las tiendas, los granjeros y las vacas. Luego, ordenamos las tiendas y los granjeros por los precios ofrecidos, y ordenamos las vacas por su producción de leche.

Después, al recorrer la lista, o bien ordeñamos la vaca de mayor producción o bien alquilamos la de menor producción, la que sea más lucrativa.

Pero ¿cómo calculamos cuánta ganancia haría la vaca de mayor producción si se ordeña? Podríamos hacerlo recorriendo linealmente las tiendas. Sin embargo, en el caso en que cada vaca puede satisfacer la oferta de cada tienda pero todas las vacas se alquilan, esto correría en $O(NM)$ , que es demasiado lento para $N = 10^5$ , $M = 10^5$ .

En cambio, después de ordenar las tiendas, podemos computar sumas de prefijos de leche/dinero y hacer búsqueda binaria (en vez de búsqueda lineal) para ver por cuántas tiendas pasa una vaca. Para el cumplimiento parcial de una oferta, podemos calcular la ganancia usando el índice lower-bound i que obtuvimos con la búsqueda binaria:

\text{sell\\_profit} = \left( \text{milk\\_prefix}[i + 1] - \left( \text{total\\_milk\\_sold} + \text{milk\\_from\\_cur\\_cow} \right) \right) \times \text{offers}[i].p_i

Implementación

Complejidad temporal: $\mathcal{O}((N + M + R) \log (N + M + R))$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
	freopen("rental.in", "r", stdin);
	freopen("rental.out", "w", stdout);
 
	int n, m, r;
	cin >> n >> m >> r;
 
	vector<int> cows(n);
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
	sort(cows.begin(), cows.end());
 
	vector<pair<int, int>> orders(m);
	for (int i = 0; i < m; i++) { cin >> orders[i].first >> orders[i].second; }
	sort(orders.begin(), orders.end(), [](pair<int, int> a, pair<int, int> b) {
		return a.second > b.second;
	});  // ordenamos por p_i
 
	// calculamos sumas de prefijos
	vector<long long> milk_pre(m + 1);
	vector<long long> cents_pre(m + 1);
	for (int i = 0; i < m; i++) {
		milk_pre[i + 1] = milk_pre[i] + orders[i].first;
		cents_pre[i + 1] = cents_pre[i] + orders[i].second * orders[i].first;
	}
 
	priority_queue<int> rent_orders;  // solo se considera y consume la orden de alquiler
	                                  // máxima, así que podemos usar una cola de prioridad
	for (int i = 0; i < r; i++) {
		int rent_order;
		cin >> rent_order;
		rent_orders.push(rent_order);
	}
 
	int rent_idx = 0, sell_idx = n - 1;  // consumimos vorazmente vacas desde los extremos
	long long total_sold = 0;
	long long total_sell_money = 0;
	long long profit = 0;
	while (rent_idx <= sell_idx) {
		// opción 1: vender toda la leche de la vaca más productiva
		int buyer_idx =
		    distance(milk_pre.begin(), lower_bound(milk_pre.begin(), milk_pre.end(),
		                                           total_sold + cows[sell_idx])) -
		    1;  // búsqueda binaria de leche total vendida + leche de la vaca actual
		long long sell_money =
		    buyer_idx < m ? (cents_pre[buyer_idx + 1] -
		                     (milk_pre[buyer_idx + 1] - (total_sold + cows[sell_idx])) *
		                         orders[buyer_idx].second -
		                     total_sell_money)
		                  : cents_pre.back() - total_sell_money;
 
		// opción 2: alquilar la vaca menos productiva
		int rent_money = rent_orders.empty() ? 0 : rent_orders.top();
 
		if (sell_money >= rent_money) {
			profit += sell_money;
			total_sold += cows[sell_idx];
			total_sell_money += sell_money;
			sell_idx--;
		} else {
			profit += rent_money;
			rent_idx++;
			rent_orders.pop();
		}
	}
	cout << profit;
}


import java.io.*;
import java.util.*;
 
public class Rental {
	// BeginCodeSnip{Shop Class}
	static class Shop {
		public int price;
		public int amt;
		public Shop(int amt, int price) {
			this.amt = amt;
			this.price = price;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("rental.in"));
 
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int n = Integer.parseInt(initial.nextToken());
		int m = Integer.parseInt(initial.nextToken());
		int r = Integer.parseInt(initial.nextToken());
 
		int[] milkAmt = new int[n];
		for (int i = 0; i < n; i++) { milkAmt[i] = Integer.parseInt(read.readLine()); }
 
		Shop[] shops = new Shop[m];
		for (int i = 0; i < m; i++) {
			StringTokenizer shop = new StringTokenizer(read.readLine());
			shops[i] = new Shop(Integer.parseInt(shop.nextToken()),
			                    Integer.parseInt(shop.nextToken()));
		}
 
		int[] rent = new int[r];
		for (int i = 0; i < r; i++) { rent[i] = Integer.parseInt(read.readLine()); }
 
		// ordenamos las vacas por producción de leche en orden decreciente
		Arrays.sort(milkAmt);
		for (int i = 0; i < n / 2; i++) {
			int temp = milkAmt[i];
			milkAmt[i] = milkAmt[milkAmt.length - i - 1];
			milkAmt[milkAmt.length - i - 1] = temp;
		}
 
		// ordenamos las tiendas por precio de venta en orden decreciente
		Arrays.sort(shops, Comparator.comparingInt(s -> - s.price));
 
		long[] milkPre = new long[m + 1];
		long[] centsPre = new long[m + 1];
		for (int i = 0; i < m; i++) {
			milkPre[i + 1] = milkPre[i] + shops[i].amt;
			centsPre[i + 1] = centsPre[i] + (long)shops[i].price * shops[i].amt;
		}
 
		// ordenamos el alquiler en orden decreciente
		Arrays.sort(rent);
		for (int i = 0; i < r / 2; i++) {
			int temp = rent[i];
			rent[i] = rent[rent.length - i - 1];
			rent[rent.length - i - 1] = temp;
		}
 
		int rentAt = 0;  // el índice del granjero hasta el que alquilamos
		int cowAt = 0;
		long totalSold = 0;
		long totalSellMoney = 0;
		long maxMoney = 0;
		while (cowAt < n) {
			// calculamos cuánto dinero puede hacer esta vaca si vendemos su leche
			int amt = milkAmt[cowAt];
			long newTotal = totalSold + amt;
			int pos = Arrays.binarySearch(milkPre, newTotal);
			if (pos < 0) { pos = -pos - 1; }
			int buyerIdx = pos - 1;
			long soldMoney;
			if (buyerIdx < m) {
				soldMoney = centsPre[buyerIdx + 1] -
				            (milkPre[buyerIdx + 1] - newTotal) * shops[buyerIdx].price -
				            totalSellMoney;
			} else {
				soldMoney = centsPre[m] - totalSellMoney;
			}
 
			// ¿alquilamos o vendemos esta vaca?
			if (rentAt >= r || soldMoney > rent[rentAt]) {  // vender
				maxMoney += soldMoney;
				totalSold = newTotal;
				totalSellMoney += soldMoney;
				cowAt++;
			} else {  // alquilar
				maxMoney += rent[rentAt];
				/*
				 * en vez de vender esta vaca, es mejor alquilar
				 * la vaca que produce menos leche
				 * (no procesamos la vaca del final de la lista)
				 */
				n--;
				rentAt++;
			}
		}
 
		PrintWriter written = new PrintWriter("rental.out");
		written.println(maxMoney);
		written.close();
	}
}


import bisect
 
with open("rental.in") as read:
	n, m, r = [int(i) for i in read.readline().split()]
 
	milk_amt = [int(read.readline()) for _ in range(n)]
	shops = [[int(i) for i in read.readline().split()] for _ in range(m)]
	rent = [int(read.readline()) for _ in range(r)]
 
# ordenamos las vacas por producción de leche en orden decreciente
milk_amt.sort(reverse=True)
# ordenamos las tiendas por precio de venta en orden decreciente
shops.sort(reverse=True, key=lambda s: s[1])
milk_pre = [0]
cents_pre = [0]
for qty, price in shops:
	milk_pre.append(milk_pre[-1] + qty)
	cents_pre.append(cents_pre[-1] + price * qty)
# ordenamos el alquiler en orden decreciente
rent.sort(reverse=True)
 
rent_at = 0  # el índice del granjero hasta el que alquilamos
cow_at = 0
total_sold = 0
total_sell_money = 0
max_money = 0
while cow_at < n:
 
	# calculamos cuánto dinero puede hacer esta vaca si vendemos su leche
	amt = milk_amt[cow_at]
	new_total = total_sold + amt
	buyer_idx = bisect.bisect_left(milk_pre, new_total) - 1
	if buyer_idx < m:
		sold_money = (
			cents_pre[buyer_idx + 1]
			- (milk_pre[buyer_idx + 1] - new_total) * shops[buyer_idx][1]
			- total_sell_money
		)
	else:
		sold_money = cents_pre[m] - total_sell_money
 
	# ¿alquilamos o vendemos esta vaca?
	if rent_at >= r or sold_money > rent[rent_at]:
		max_money += sold_money
		total_sold = new_total
		total_sell_money += sold_money
		cow_at += 1
	else:
		max_money += rent[rent_at]
		"""
		en vez de vender esta vaca, es mejor alquilar
		la vaca que produce menos leche
		(no procesamos la vaca del final de la lista)
		"""
		n -= 1
		rent_at += 1
 
print(max_money, file=open("rental.out", "w"))