Skip to Content
CTRL K

Blocking Elements

Análisis oficial (C++) 

Explicación

Antes de empezar, anexamos un 00 al final del arreglo y forzamos que ese elemento siempre esté bloqueado. Esto hace más fácil hablar del problema y no afecta la respuesta.

Podemos hacer búsqueda binaria sobre la respuesta; para ver cómo, veamos cómo podemos comprobar si un costo de a lo sumo CC es posible.

Sea dp[i]\texttt{dp}[i] el costo mínimo considerando solo elementos hasta el índice ii. Como tomamos el máximo sobre las sumas de los segmentos bloqueados, no tenemos que preocuparnos por ellos mientras cada uno sea menor que CC; solo tenemos que preocuparnos por la suma de los elementos bloqueados.

Si jj es el menor elemento desde el que podemos empezar a bloquear sin que la suma del nuevo segmento que creamos exceda CC, entonces

dp[i]=min⁡j≤x<idp[x]+ai dp[i] = \min_{j \le x < i} dp[x] + a_i

lo cual se puede calcular usando un Árbol de Segmentos.

Implementación

Complejidad temporal: O(nlog⁡nlog⁡S)O(n \log n \log S), donde S=∑i=1naiS=\sum_{i=1}^n a_i.

#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
// BeginCodeSnip{Segment Tree (from the module)}
template <class T> class MinSegmentTree {
  private:
	const T DEFAULT = std::numeric_limits<T>().max();
 
	int len;
	vector<T> segtree;
 
  public:
	MinSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = std::min(segtree[ind], segtree[ind ^ 1]);
		}
	}
 
	T range_min(int start, int end) {
		T min = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { min = std::min(min, segtree[start++]); }
			if (end % 2 == 1) { min = std::min(min, segtree[--end]); }
		}
		return min;
	}
};
// EndCodeSnip
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int len;
		std::cin >> len;
		vector<int> arr(len);
		long long max_cost = 0;
		for (int &i : arr) {
			std::cin >> i;
			max_cost += i;
		}
 
		// force a blocking element at the last position without affecting the answer
		arr.push_back(0);
		len++;
 
		long long lo = 0;
		long long hi = max_cost;
		long long valid = -1;
		while (lo <= hi) {
			long long mid = (lo + hi) / 2;
 
			// the minimum cost to block up to a certain position
			// given that the last element is blocked
			MinSegmentTree<long long> min_cost(len);
			int lowest_start = -1;
			long long curr_sum = 0;
			for (int i = 0; i < len; i++) {
				curr_sum += i > 0 ? arr[i - 1] : 0;
				while (curr_sum > mid) {
					lowest_start++;
					curr_sum -= arr[lowest_start];
				}
				long long best = lowest_start == -1 ? 0 : INT64_MAX;
				// calculate the best starting position to block from
				best = std::min(best, min_cost.range_min(std::max(lowest_start, 0), i));
				min_cost.set(i, best + arr[i]);
			}
 
			if (min_cost.range_min(len - 1, len) <= mid) {
				valid = mid;
				hi = mid - 1;
			} else {
				lo = mid + 1;
			}
		}
 
		cout << valid << '\n';
	}
}
Fundamentos