William and Robot

Explicación

Primero, nótese que el único requisito para una solución válida es que, para cualquier número par $k \leq n$, William debe haber seleccionado a lo sumo $\frac{k}{2}$ enteros de entre los primeros $k$ enteros. Es imposible seleccionar más de $\frac{k}{2}$ enteros en los primeros $k$ enteros, porque el robot se habrá llevado todos los otros $\frac{k}{2}$ enteros para cuando podamos elegir el siguiente. Nótese también que es posible “guardar” elecciones, ya que se pueden elegir menos de $\frac{k}{2}$ enteros para $k < n$, lo que permite elegir más para un $k$ más grande.

Por ejemplo, si tuviéramos un arreglo de tamaño $4$, podríamos seleccionar cualquiera de los dos primeros elementos y cualquiera de los dos últimos, seleccionando exactamente $\frac{k}{2}$ enteros tanto para $k = 2$ como para $k = 4$. Como alternativa, podríamos seleccionar ambos de los dos últimos elementos, seleccionando 0 enteros para $k = 2$ y $2$ enteros para $k = 4$. Nótese que no podemos tomar el primero y el segundo elemento, porque el robot se lleva el que no elijamos.

Para resolver este problema, podemos iterar $k$ de $1$ a $n$ y mantener una cola de prioridad con los números seleccionados de forma tentativa por William hasta el momento. Para cada $k$ empujamos $a_k$ a la cola de prioridad y, si $k$ es par, extraemos el menor elemento de la cola de prioridad mientras la cantidad de enteros tomados sea mayor que $k/2$.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<int> a(n);
	for (int &i : a) { cin >> i; }
 
	// guarda los números seleccionados actualmente
	priority_queue<int, vector<int>, greater<int>> taken;
 
	for (int i = 0; i < n; ++i) {
		taken.push(a[i]);
		if (i & 1) taken.pop();
	}
 
	long long ans = 0;
	while (!taken.empty()) {
		ans += taken.top();
		taken.pop();
	}
 
	cout << ans << endl;
}

import java.io.*;
import java.util.*;
 
public class WilliamAndRobot {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int n = io.nextInt();
		int[] a = new int[n];
 
		for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }
 
		PriorityQueue<Integer> taken = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			taken.offer(a[i]);
			if (i % 2 == 1) { taken.poll(); }
		}
 
		long ans = 0;
		while (!taken.isEmpty()) { ans += taken.poll(); }
 
		io.println(ans);
		io.close();
	}
 
	// CodeSnip{Kattio}
}

import heapq
 
n = int(input())
a = list(map(int, input().split()))
 
taken = []
for i in range(n):
	heapq.heappush(taken, a[i])
	if i % 2 == 1:
		heapq.heappop(taken)
 
print(sum(taken))