The Party and Sweets

Editorial oficial 

Solución (voraz)

Consideremos el siguiente ejemplo:

2 2
0 1
1 0

La respuesta a este ejemplo es $-1$ porque el chico $2$ termina dándole a la chica $2$ demasiados dulces, incluso si el chico $2$ le da a la chica $2$ la cantidad mínima de dulces que podría darle, que es $1$. Sin embargo, la chica $2$ recibió un máximo de ningún dulce, lo que lo hace imposible.

Si un solo chico da más dulces de los que una chica recibió, entonces cualquier disposición de dulces es imposible con las restricciones. Más formalmente, si

entonces la respuesta es $-1$.

Si la entrada tiene una disposición de dulces que cumple las restricciones dadas, entonces podemos hallar la respuesta de forma voraz.

Como el objetivo es minimizar la cantidad total de dulces entregados, primero consideremos una cota inferior de la respuesta. Como la menor cantidad de dulces que el chico $i$ le da a cada chica es $b_i$, entrega en total al menos $b_i \cdot m$ dulces. Así, la respuesta a este problema está acotada inferiormente por $\sum\limits_{i=1}^{n} b_i \cdot m$.

Aún no hemos terminado. La suma anterior no necesariamente satisface la condición de que $g_i$ es la cantidad máxima de dulces que recibió una sola chica. Cada chica $j$ tiene algún chico $i$ que le dio $g_j$ dulces en lugar de $b_i$ dulces. Esto sube nuestra cota inferior en $g_j-b_i$. Quisiéramos elegir $i$ tal que $b_i$ sea máximo. Como sabemos que $\max(b) \leq \min(g)$, siempre elegiríamos al chico que da más dulces.

Sin embargo, este chico todavía debe dar $b_i$ dulces a alguna chica; así, si ningún $g_j$ es igual a $b_i$, entonces necesita haberle dado a alguna chica $b_i$ dulces y el chico que da la segunda mayor cantidad de dulces puede darle a esta chica su máximo de dulces.

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

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main() {
 
	int n, m;
	cin >> n >> m;
	vector<int> b(n), g(m);
	ll res = 0;
 
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		res += b[i];
	}
 
	for (int i = 0; i < m; i++) { cin >> g[i]; }
 
	// Cota inferior inicial de la respuesta
	res *= m;
 
	sort(b.begin(), b.end());
	sort(g.begin(), g.end());
 
	// Si es imposible satisfacer las restricciones
	if (b[n - 1] > g[0]) {
		cout << -1;
		return 0;
	}
 
	for (int i = 1; i < m; i++) { res += g[i] - b[n - 1]; }
 
	if (g[0] != b[n - 1]) { res += g[0] - b[n - 2]; }
 
	cout << res << endl;
}

import java.io.*;
import java.util.*;
 
public class ThePartyAndSweets {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int m = io.nextInt();
 
		int[] b = new int[n];
		int[] g = new int[m];
		long res = 0;
 
		for (int x = 0; x < n; x++) {
			b[x] = io.nextInt();
			res += b[x];
		}
 
		for (int x = 0; x < m; x++) { g[x] = io.nextInt(); }
 
		// Cota inferior inicial de la respuesta
		res *= m;
 
		Arrays.sort(b);
		Arrays.sort(g);
 
		// Si es imposible satisfacer las restricciones
		if (b[n - 1] > g[0]) {
			io.println(-1);
			io.close();
			System.exit(0);
		}
 
		for (int i = 1; i < m; i++) { res += (g[i] - b[n - 1]); }
 
		if (g[0] != b[n - 1]) { res += (g[0] - b[n - 2]); }
 
		io.println(res);
		io.close();
	}
	// CodeSnip{Kattio}
}