Cow College

Solución

Explicación

El problema principal es cómo calcular de forma eficiente la cantidad de dinero que gana FJ.

Para ello, podemos ordenar nuestra lista de vacas antes de empezar a procesarlas. En nuestra lista ordenada, observemos que la matrícula que gana FJ en el índice $i$ (empezando desde 0) es $c_i \cdot (N-i)$ .

Por ejemplo, veamos la entrada de ejemplo:


4
1 6 4 6

Si ordenamos la lista de modo que quede $[1, 4, 6, 6]$ y tomamos $i$ igual a $1$ , FJ ganará $c_1 \cdot (N-1)=4 \cdot 3=12$ unidades de dinero.

Con este conocimiento, ahora podemos recorrer la lista, probando todos los valores de $i$ y tomando la matrícula máxima que gana FJ.

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<int> tuition(n);
	for (int &t : tuition) { cin >> t; }
 
	sort(tuition.begin(), tuition.end());
 
	int best_tuition = 0;
	long long best_money = 0;
	for (int i = 0; i < n; i++) {
		// Aplicar la fórmula del editorial
		long long curr_tuition = (long long)tuition[i] * (n - i);
		if (curr_tuition > best_money) {
			best_tuition = tuition[i];
			best_money = curr_tuition;
		}
	}
 
	cout << best_money << ' ' << best_tuition << endl;
}


import java.util.*;
 
public class CowCollege {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		int[] tuition = new int[n];
		for (int i = 0; i < n; i++) { tuition[i] = sc.nextInt(); }
 
		Arrays.sort(tuition);
 
		int bestTuition = 0;
		long bestMoney = 0;
		for (int i = 0; i < n; i++) {
			// Aplicar la fórmula del editorial
			long currTuition = (long)tuition[i] * (n - i);
			if (currTuition > bestMoney) {
				bestTuition = tuition[i];
				bestMoney = currTuition;
			}
		}
 
		System.out.println(bestMoney + " " + bestTuition);
	}
}


n = int(input())
tuition = sorted(map(int, input().split()))
 
best_tuition = 0
best_money = 0
for i in range(n):
	# Aplicar la fórmula del editorial
	curr_tuition = tuition[i] * (n - i)
	if curr_tuition > best_money:
		best_tuition = tuition[i]
		best_money = curr_tuition
 
print(best_money, best_tuition)