Dishwashing

Solución alternativa — búsqueda binaria

Podemos hacer búsqueda binaria sobre el prefijo más largo posible. Un prefijo de longitud $i-1$ es simplemente un prefijo de longitud $i$ sin un plato; si es posible lavar todos los platos del prefijo $i$ entonces también debe ser posible lavar un prefijo de $i-1$ . Ahora solo necesitamos simular el apilado y el lavado. Como describe el análisis oficial, si el plato $A$ está encima del plato $B$ en la misma pila, entonces $A$ debe ser menor que $B$ , o de lo contrario no podemos acceder al plato que está debajo.

Podemos colocar de forma voraz cada plato en la pila $i$ si el plato de arriba de la pila $i$ es mayor que nuestro plato actual y es el más pequeño entre todas las demás pilas enjabonadas. Esto es porque siempre es más óptimo satisfacer una restricción más estricta, en vez de sobreescribir una más amplia si colocamos el plato en otra pila cuyo plato de arriba no es el más pequeño posible.

Implementación

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream fin("dishes.in");
	int n;
	fin >> n;
	vector<int> order(n);
	for (int i = 0; i < n; i++) { fin >> order[i]; }
 
	// returns true if dishes with indexes [0, end_index) can be washed
	auto prefix_washable = [&](int end_index) -> bool {
		deque<int> not_washed;
		for (int i = 0; i < end_index; i++) { not_washed.push_back(order[i]); }
		sort(not_washed.begin(), not_washed.end());
 
		// Each array represents a separate soapy stack
		deque<vector<int>> soapy_stacks;
 
		for (int i = 0; i < end_index; i++) {
			int plate = order[i];
 
			// binary search for the first stack it can be placed
			int l = -1, r = soapy_stacks.size();
			while (l < r - 1) {
				int mid = (l + r) / 2;
				if (soapy_stacks[mid].back() > plate) {
					r = mid;
				} else {
					l = mid;
				}
			}
 
			// not able to be placed in any existing stack
			if (r == soapy_stacks.size()) {
				// create new stack
				soapy_stacks.push_back({plate});
			} else {
				soapy_stacks[r].push_back(plate);
			}
 
			// while are able to wash a plate, wash it
			while (!soapy_stacks.empty() &&
			       soapy_stacks.front().back() == not_washed.front()) {
				soapy_stacks.front().pop_back();
				not_washed.pop_front();
				// if first stack is empty, remove it
				if (soapy_stacks.front().empty()) { soapy_stacks.pop_front(); }
			}
		}
 
		// returns true if every plate is washed
		return not_washed.empty();
	};
 
	// binary search for the longest possible prefix
	int l = 0, r = n + 1;
	while (l < r - 1) {
		int mid = (l + r) / 2;
		if (prefix_washable(mid)) {
			l = mid;
		} else {
			r = mid;
		}
	}
	ofstream("dishes.out") << l << endl;
}