UVa Online Judge – 11678 – Cards’ Exchange

El link del problema es el siguiente:
11678 – Cards’ Exchange

En el problema nos describen que tenemos 2 conjuntos de cartas, y queremos ver el máximo numero de intercambios que se pueden realizar.
El problema es de tipo Ad Hoc.

La forma en la que yo aborde el problema es utilizando conjuntos.
Tenemos que cada conjunto de cartas puede tener repetidos, así que los eliminamos y la forma mas sencilla es utilizando un Set.
Una vez tenemos los dos conjuntos ya sin cartas repetidas, podemos obtener que cartas pertenecen a los dos conjuntos, esto se veria como una operacion de Interseccion en conjuntos.
Y por ultimo, una vez conocido el numero de cartas que comparten los dos conjuntos la solución esta dado por el mínimo de las diferencias del numero de cartas que tiene cada jugador menos el numero de cartas que comparten en común.

Ejemplo:

1 1 2 3 5 7 8 8 9 15  //j1
2 2 2 3 4 6 10 11 11  //j2

Set del J1
1 2 3 5 7 8 9 15   tamaño = 8
Set del J2
2 3 4 6 10 11    tamaño = 6
Cartas en común (union)
2 3

Como se nota, el numero de cartas en común son 2, por lo tanto a lo mas pueden intercambiar (8-2) o (6-2), y de ahí hay que tomar el mínimo, en este caso 4.

 

Codigo en C++