Towers
Enfoque voraz: siempre añadir el siguiente cubo encima de la torre con el cubo más pequeño posible en la cima (o crear una torre nueva si no es posible).
¡Equivalente a la subsecuencia no decreciente más larga!
Es importante notar que no podemos usar fuerza bruta para hallar la torre con el cubo más pequeño posible en la cima porque eso daría complejidad , que es demasiado lenta.
Solución 1 - Búsqueda binaria + arreglo dinámico
Podemos guardar las torres existentes usando un arreglo dinámico, donde el valor de cada torre es el tamaño del cubo de la cima. Para cada cubo, podemos ejecutar búsqueda binaria upper bound sobre el arreglo para hallar la torre con el cubo de cima más pequeño que sea estrictamente mayor que el cubo actual. Si encontramos una torre adecuada, añadimos el cubo a la cima y cambiamos el valor de la torre al tamaño del cubo. Si no existe tal torre, añadimos una torre nueva al final del arreglo. De este modo, mantenemos el arreglo de torres en orden (intenta demostrarlo por tu cuenta). Nuestra respuesta será el tamaño del arreglo después de procesar todos los cubos.
Implementación
Complejidad temporal:
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define pb push_back
#define sz(x) (int)(x).size()
int n;
vi x; // stores towers in non-decreasing order
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
int z;
cin >> z;
int lo = 0, hi = sz(x);
while (lo < hi) {
int mid = (lo + hi) / 2;
if (x[mid] > z) hi = mid;
else lo = mid + 1;
}
if (lo == sz(x)) x.pb(z); // create new tower
else x[lo] = z; // add to tower
}
cout << sz(x);
}import java.io.*;
import java.util.*;
public class Towers {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int[] cubes = new int[n];
for (int i = 0; i < n; i++) { cubes[i] = io.nextInt(); }
// Stores towers in non-decreasing order
List<Integer> towers = new ArrayList<>();
for (int i = 0; i < n; i++) {
// Upper bound binary search
int lo = 0;
int hi = towers.size();
while (lo < hi) {
int mid = (lo + hi) / 2;
if (cubes[i] >= towers.get(mid)) lo = mid + 1;
else hi = mid;
}
// If there aren't any suitable towers, append new tower to end of
// array
if (lo == towers.size()) {
towers.add(cubes[i]);
}
// If there exists a satisfying tower, add the cube to that tower
// and update the top element of the tower
else {
towers.set(lo, cubes[i]);
}
}
io.println(towers.size());
io.close();
}
// CodeSnip{Kattio}
}input()
# Store the topmost cube of each tower
towers = []
for cube in map(int, input().split()):
# Binary search
left = 0
right = len(towers) - 1
tower_idx = -1
while left <= right:
mid = (left + right) // 2
if towers[mid] <= cube:
left = mid + 1
else:
right = mid - 1
tower_idx = mid
# If there exists a satisfying tower, add the cube to that tower and update
# the top element of the tower
if tower_idx != -1:
towers[tower_idx] = cube
# If there aren't any suitable towers, append new tower to end of array
else:
towers.append(cube)
print(len(towers))Solución 2 - Multiconjunto
En este enfoque, guardamos las torres usando un multiconjunto ordenado (que se puede
representar como un
TreeMap en
Java), donde el valor de cada torre es el tamaño del cubo de la cima. Para cada cubo,
podemos usar métodos de la librería (upper_bound en C++, higherKey en Java) para hallar
la torre de menor valor con un valor estrictamente mayor que el cubo. Si
encontramos una torre adecuada, añadimos el cubo a la cima y cambiamos el valor de la torre
al tamaño del cubo, quitando el valor anterior de la torre del conjunto y
añadiendo el nuevo. Si no existe tal torre, añadimos una torre nueva al
conjunto. Nuestra respuesta será el número total de torres en el multiconjunto (esto
requiere un poco de trabajo extra en Java) después de procesar todos los cubos.
Implementación
Complejidad temporal:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n;
multiset<int> ans;
for (int i = 0; i < n; ++i) {
cin >> k;
auto it = ans.upper_bound(k);
// Find the tower having the element that is just larger than k to add
// k to. If it doesn't exist then we create a new tower.
if (it == ans.end()) ans.insert(k);
else {
// If there exists a satisfying tower, add k to that tower and
// update the top element of the tower
ans.erase(it);
ans.insert(k);
}
}
cout << ans.size();
return 0;
}import java.io.*;
import java.util.*;
public class Towers {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int[] cubes = new int[n];
for (int i = 0; i < n; i++) { cubes[i] = io.nextInt(); }
// Maps tower value to frequency
TreeMap<Integer, Integer> towers = new TreeMap<>();
for (int i = 0; i < n; i++) {
// If there are no suitable towers, add another tower to the set
if (towers.higherKey(cubes[i]) == null) {
towers.put(cubes[i], towers.getOrDefault(cubes[i], 0) + 1);
}
// If there exists a satisfying tower, add the cube to that tower
// and update the top element of the tower
else {
int size = towers.higherKey(cubes[i]);
towers.put(size, towers.get(size) - 1);
if (towers.get(size) == 0) { towers.remove(size); }
towers.put(cubes[i], towers.getOrDefault(cubes[i], 0) + 1);
}
}
// Calculate total number of towers
int ans = 0;
for (int i : towers.values()) { ans += i; }
io.println(ans);
io.close();
}
// CodeSnip{Kattio}
}from bisect import bisect
input()
# Store the topmost cube of each tower
towers = []
for cube in map(int, input().split()):
tower_idx = bisect(towers, cube)
# If there exists a satisfying tower, add the cube to that tower and update
# the top element of the tower
if tower_idx < len(towers):
towers[tower_idx] = cube
# If there aren't any suitable towers, append new tower to end of array
else:
towers.append(cube)
print(len(towers))