Yet Another Tournament

Explicación

Primero, observemos que los resultados entre oponentes se conocen de antemano: el oponente $i$ siempre vence al oponente $j$ si $i > j$ , así que el oponente $i$ tiene exactamente $i - 1$ victorias de los partidos entre oponentes, independientemente de lo que hagas.

Cuando juegas contra el oponente $i$ :

Si lo vences: termina con $i - 1$ victorias.
Si pierdes contra él: termina con $i$ victorias (gana una sobre ti).

Contar oponentes que te vencen

Si vences a un subconjunto $S$ de oponentes (con $|S| = k$ ), tienes $k$ victorias. Los oponentes con índice $\geq k + 2$ siempre terminan con más victorias que tú. El único oponente en el límite es el oponente $k + 1$ : tiene exactamente $k$ victorias de otros partidos, y te vence si perdiste contra él, lo que lo pone por encima de ti. Así, vencer al oponente $k + 1$ te ahorra exactamente un puesto.

Estrategia óptima

Iteramos sobre cada $k$ válido (número de oponentes que vences) y calculamos el mejor puesto alcanzable:

Caso 1: Vencer cualesquiera $k$ oponentes dentro del presupuesto $m$ . De forma voraz tomamos los $k$ oponentes más baratos y comprobamos la factibilidad con sumas de prefijos sobre los costos ordenados. Esto da el puesto $n - k + 1$ .
Caso 2: Vencer $k$ oponentes, incluyendo específicamente al oponente $k + 1$ , dentro del presupuesto $m$ . Sacamos al oponente $k + 1$ de consideración, tomamos los $k - 1$ oponentes restantes más baratos, y sumamos $a_{k+1}$ al costo. Si esto cabe en $m$ , el puesto mejora a $n - k$ .

Tomamos el puesto mínimo sobre todos los $k$ válidos.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t;
	cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
 
		vector<int> a(n + 1);
		for (int i = 1; i <= n; i++) { cin >> a[i]; }
 
		vector<int> sorted_a(a.begin() + 1, a.end());
		sort(sorted_a.begin(), sorted_a.end());
 
		// prefix[i] = suma de los i oponentes más baratos
		vector<int> prefix(n + 1);
		for (int i = 0; i < n; i++) { prefix[i + 1] = prefix[i] + sorted_a[i]; }
 
		int ans = n + 1;
 
		for (int k = 0; k <= n; k++) {
			if (prefix[k] > m) break;
 
			// caso 1: si podemos vencer cualesquiera k oponentes, nuestro puesto es al menos n - k + 1.
			ans = min(ans, n - k + 1);
 
			// caso 2: si también podemos vencer al oponente k+1, nuestro puesto mejora a n - k.
			if (k + 1 > n) continue;
			int cost_with;
 
			if (k == 0) {
				cost_with = a[k + 1];
			} else {
				// los k-1 más baratos tras quitar al oponente k+1, más a[k+1]
				int excl;
				if (a[k + 1] <= sorted_a[k - 1]) {
					excl = prefix[k] - a[k + 1];
				} else {
					excl = prefix[k - 1];
				}
 
				cost_with = excl + a[k + 1];
			}
 
			if (cost_with <= m) { ans = min(ans, n - k); }
		}
 
		cout << ans << '\n';
	}
}