Skip to Content
CTRL K

Save the Nature

Editorial oficial 

Explicación

Hacemos búsqueda binaria sobre la respuesta para el número mínimo de tickets, tt, a vender para que la contribución ecológica total sea al menos kk.

Intentemos determinar la contribución máxima alcanzable con tt tickets.

El problema indica que solo el x%x\% del aa-ésimo ticket y el y%y\% del bb-ésimo ticket pueden contribuir a la contribución ecológica total. Podemos precomputar estos multiplicadores pctpct (ya sea 00, xx, yy, o x+yx+y según el ticket) sobre tt tickets, y luego emparejar de forma voraz el multiplicador más grande con el ticket de mayor valor. Esto se puede hacer ordenando los multiplicadores pctpct y los tickets pp en orden decreciente; entonces la contribución ecológica total máxima sería ∑i=1tpi⋅pcti\sum\limits_{i=1}^{t} p_i \cdot pct_i.

Implementación

Complejidad temporal: O(Nlog⁡2N)\mathcal{O}(N\log^2 N)

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int n;
vector<ll> p;
 
ll x, a, y, b, k;
 
bool works(int sell_tickets) {
	vector<ll> percentages(sell_tickets);
 
	// Sumar x% a cada a-ésimo ticket.
	for (int i = a - 1; i < sell_tickets; i += a) { percentages[i] += x; }
 
	// Sumar y% a cada b-ésimo ticket
	for (int i = b - 1; i < sell_tickets; i += b) { percentages[i] += y; }
 
	sort(percentages.begin(), percentages.end(), greater<ll>());
 
	ll cur = 0;
	for (int i = 0; i < sell_tickets; i++) { cur += percentages[i] * p[i] / 100; }
 
	return cur >= k;
}
 
void solve() {
	cin >> n;
	p.resize(n);
 
	for (int i = 0; i < n; i++) { cin >> p[i]; }
 
	sort(p.begin(), p.end(), greater<ll>());
 
	cin >> x >> a >> y >> b >> k;
 
	int l = 0, r = n, ans = -1;
 
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (works(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
 
	cout << ans << endl;
}
 
int main() {
	int q;
	cin >> q;
	for (int i = 1; i <= q; i++) { solve(); }
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
 
public final class SaveNature {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int queryNum = Integer.parseInt(read.readLine());
		for (int q = 0; q < queryNum; q++) {
			int ticketNum = Integer.parseInt(read.readLine());
			long[] tickets = Arrays.stream(read.readLine().split(" "))
			                     .mapToLong(Long::parseLong)
			                     .toArray();
			Arrays.sort(tickets);
 
			// primero el porcentaje de los ingresos, luego la frecuencia
			int[] prog1 = Arrays.stream(read.readLine().split(" "))
			                  .mapToInt(Integer::parseInt)
			                  .toArray();
			int[] prog2 = Arrays.stream(read.readLine().split(" "))
			                  .mapToInt(Integer::parseInt)
			                  .toArray();
			long minRevenue = Long.parseLong(read.readLine());
			// la frecuencia de ambos programas incluyendo un solo ticket
			long comboFreq = (long)prog1[1] * prog2[1] / gcd(prog1[1], prog2[1]);
 
			int lo = 0;
			int hi = ticketNum;
			int valid = -1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
				// todos los tickets posibles que se pueden usar para salvar la naturaleza
				int[][] helpChances =
				    new int[][] {{prog1[0] + prog2[0], ((int)(mid / comboFreq))},
				                 {prog1[0], (int)(mid / prog1[1] - mid / comboFreq)},
				                 {prog2[0], (int)(mid / prog2[1] - mid / comboFreq)}};
				// ordenar las chances, el mayor porcentaje primero
				Arrays.sort(helpChances, Comparator.comparingInt(c -> - c[0]));
 
				// como los tickets están ordenados de forma creciente, recorremos
				// en reversa
				int ticketAt = ticketNum - 1;
				long revenue = 0;
				for (int[] chance : helpChances) {
					for (int i = 0; i < chance[1]; i++) {
						revenue += tickets[ticketAt--] * chance[0] / 100;
					}
				}
				if (revenue >= minRevenue) {
					valid = mid;
					hi = mid - 1;
				} else {
					lo = mid + 1;
				}
			}
			System.out.println(valid);
		}
	}
 
	private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}
from math import gcd
 
for _ in range(int(input())):
	ticket_num = int(input())
	tickets = sorted([int(i) for i in input().split()], reverse=True)
	prog1 = [int(i) for i in input().split()]
	prog2 = [int(i) for i in input().split()]
	min_revenue = int(input())
	# la frecuencia de ambos programas incluyendo un solo ticket
	combo_freq = prog1[1] * prog2[1] // gcd(prog1[1], prog2[1])
 
	lo = 0
	hi = ticket_num
	valid = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		# todos los tickets posibles que se pueden usar para salvar la naturaleza
		help_chances = sorted(
			[
				[prog1[0] + prog2[0], mid // combo_freq],
				[prog1[0], mid // prog1[1] - mid // combo_freq],
				[prog2[0], mid // prog2[1] - mid // combo_freq],
			],
			reverse=True,
		)
 
		ticket_at = 0
		revenue = 0
		"""
		vender los tickets, con el ticket más caro
		y el mayor porcentaje primero para maximizar los ingresos
		"""
		for ch in help_chances:
			for _ in range(ch[1]):
				revenue += tickets[ticket_at] * ch[0] // 100
				ticket_at += 1
 
		if revenue >= min_revenue:
			valid = mid
			hi = mid - 1
		else:
			lo = mid + 1
	print(valid)
Fundamentos