Skip to Content
CTRL K

Ciel and Duel

Editorial oficial (C++) 

Explicación

Como no hace falta derrotar necesariamente todas las cartas de Jiro, hay dos caminos posibles:

  1. Concentrarse en obtener el máximo daño sin derrotar todas las cartas de Jiro.
  2. Concentrarse en derrotar todas las cartas de Jiro y luego hacer daño directo.

Resolveremos cada parte de forma independiente.

En el primer enfoque, nótese que, como no buscamos derrotar todas las cartas, no ganamos nada atacando las cartas de defensa de Jiro. Así, emparejamos las cartas de ataque más débiles de Jiro contra nuestras cartas de ataque más fuertes.

En el segundo enfoque, para no perder daño de ataque, emparejamos las cartas de Jiro con la carta más chica que sea mayor que ellas.

Al final, devolvemos la cantidad mayor.

Implementación

Complejidad temporal: O(NM)\mathcal{O}(NM)

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
using std::endl;
using std::string;
using std::vector;
 
struct Card {
	// 1 -> ATK | 0 -> DEF
	bool type;
	int strength;
};
 
int main() {
	int n, m;
	std::cin >> n >> m;
 
	vector<Card> jiro;
	vector<Card> ciel;
 
	for (int i = 0; i < n; i++) {
		string type;
		int strength;
		std::cin >> type >> strength;
 
		jiro.push_back({type == "ATK", strength});
	}
 
	for (int i = 0; i < m; i++) {
		int strength;
		std::cin >> strength;
 
		ciel.push_back({1, strength});
	}
 
	// primer caso: solo pegarle a ATK + asignar cartas débiles con cartas fuertes
 
	// ordenamos por tipo y luego por fuerza
	std::sort(jiro.begin(), jiro.end(), [](const Card &a, const Card &b) {
		if (a.type == b.type) { return a.strength < b.strength; }
		return a.type > b.type;
	});
 
	std::sort(ciel.begin(), ciel.end(),
	          [](const Card &a, const Card &b) { return a.strength > b.strength; });
 
	int appr1 = 0;
	for (int i = 0; i < std::min(n, m); i++) {
		// cortamos si atacamos cartas DEF o si no ganamos nada
		if (!jiro[i].type || ciel[i].strength <= jiro[i].strength) { break; }
 
		appr1 += ciel[i].strength - jiro[i].strength;
	}
 
	std::reverse(jiro.begin(), jiro.end());
	std::reverse(ciel.begin(), ciel.end());
 
	vector<bool> done(m);
 
	int appr2 = 0;
	for (int i = 0; i < n; i++) {
		bool fnd = false;
 
		for (int j = 0; j < m; j++) {
			// si no usamos j y esta carta puede vencer a la de Jiro
			if (!done[j] && ((jiro[i].type && ciel[j].strength >= jiro[i].strength) ||
			                 (!jiro[i].type && ciel[j].strength > jiro[i].strength))) {
				done[j] = true;
 
				if (jiro[i].type) { appr2 += ciel[j].strength - jiro[i].strength; }
 
				fnd = true;
				break;
			}
		}
 
		// si no podemos hacer daño directo, imprimimos el primer enfoque
		if (!fnd) {
			std::cout << appr1 << endl;
			return 0;
		}
	}
 
	// sumamos todo el daño directo hecho
	for (int i = 0; i < m; i++) {
		if (!done[i]) { appr2 += ciel[i].strength; }
	}
 
	std::cout << std::max(appr2, appr1) << endl;
}
import java.io.*;
import java.util.*;
 
public class Main {
	static class Card {
		// 1 -> ATK | 0 -> DEF
		public boolean type;
		public int strength;
 
		Card(boolean type, int strength) {
			this.type = type;
			this.strength = strength;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		List<Card> jiro = new ArrayList<>();
		List<Card> ciel = new ArrayList<>();
 
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			String type = st.nextToken();
			int strength = Integer.parseInt(st.nextToken());
			jiro.add(new Card("ATK".equals(type), strength));
		}
 
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int strength = Integer.parseInt(st.nextToken());
			ciel.add(new Card(true, strength));
		}
 
		// primer caso: solo pegarle a ATK + asignar cartas débiles con cartas fuertes
 
		// ordenamos por tipo (ATK primero) y luego por fuerza (ascendente)
		jiro.sort(Comparator.comparing((Card c) -> c.type)
		              .reversed()
		              .thenComparingInt(c -> c.strength));
 
		// ordenamos ciel por fuerza (descendente)
		ciel.sort(Comparator.comparingInt((Card c) -> c.strength).reversed());
 
		int appr1 = 0;
		for (int i = 0; i < Math.min(n, m); i++) {
			// cortamos si atacamos cartas DEF o si no ganamos nada
			if (!jiro.get(i).type || ciel.get(i).strength <= jiro.get(i).strength) {
				break;
			}
			appr1 += ciel.get(i).strength - jiro.get(i).strength;
		}
 
		Collections.reverse(jiro);
		Collections.reverse(ciel);
 
		boolean[] done = new boolean[m];
 
		int appr2 = 0;
		for (int i = 0; i < n; i++) {
			boolean fnd = false;
 
			for (int j = 0; j < m; j++) {
				// si no usamos j y esta carta puede vencer a la de Jiro
				if (!done[j] && ((jiro.get(i).type &&
				                  ciel.get(j).strength >= jiro.get(i).strength) ||
				                 (!jiro.get(i).type &&
				                  ciel.get(j).strength > jiro.get(i).strength))) {
					done[j] = true;
 
					if (jiro.get(i).type) {
						appr2 += ciel.get(j).strength - jiro.get(i).strength;
					}
 
					fnd = true;
					break;
				}
			}
 
			// si no podemos hacer daño directo, imprimimos el primer enfoque
			if (!fnd) {
				System.out.println(appr1);
				return;
			}
		}
 
		// sumamos todo el daño directo hecho
		for (int i = 0; i < m; i++) {
			if (!done[i]) { appr2 += ciel.get(i).strength; }
		}
 
		System.out.println(Math.max(appr2, appr1));
	}
}
Fundamentos