Deforestation

Explicación

Podemos encarar esta pregunta como talar la cantidad máxima de árboles satisfaciendo todas las restricciones.

Primero, mantenemos una lista que contiene tanto los árboles como los intervalos, ordenada por el extremo izquierdo de los intervalos y las posiciones de los árboles. Luego, podemos recorrer esta lista de izquierda a derecha.

Consideremos el caso en que encontramos un intervalo mientras procesamos. Sea $\text{cur}$ la cantidad actual de árboles talados, que representa la respuesta actual. Cuando añadimos un intervalo nuevo, impone una restricción sobre la cantidad de árboles que se pueden talar en el rango de ese intervalo. Formalmente, si $\text{present}$ es la cantidad actual de árboles presentes en ese intervalo, entonces a lo sumo $\text{cut} = \text{present} - t_i$ árboles se pueden talar en el rango de ese intervalo. El valor de la respuesta al final de este intervalo es por tanto a lo sumo $\text{cur} + \text{cut}$ .

Para mantener estas condiciones, podemos usar una cola de prioridad que lleva la menor cantidad de árboles que se pueden talar en el momento dado. Al procesar un árbol, mientras no se haya alcanzado ya la cantidad máxima de árboles de los intervalos actuales, podemos talar de forma voraz el árbol actual.

Se puede mostrar que esta estrategia es óptima. Si en su lugar eligiéramos talar un árbol futuro, podría afectar tanto intervalos futuros como actuales, reduciendo potencialmente el total de árboles que podemos talar. En cambio, talar el árbol actual solo afecta los intervalos actuales, lo que lo hace siempre la elección óptima.

Implementación

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

C++PythonJava


 
#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> x(n);
	for (auto &d : x) cin >> d;
 
	sort(x.begin(), x.end());
 
	vector<array<int, 4>> critical_points;
	// Procesar intervalos e insertarlos en la lista de puntos críticos, usando sus
	// cotas derecha e izquierda, y la cantidad de árboles del intervalo menos la
	// restricción
	for (int i = 0; i < k; i++) {
		int left, right, t;
		cin >> left >> right >> t;
		auto right_amt = upper_bound(x.begin(), x.end(), right);
		auto left_amt = lower_bound(x.begin(), x.end(), left);
		critical_points.push_back({l, 0, r, (right_amt - left_amt) - t});
	}
 
	// Añadir árboles a la lista de puntos críticos usando su posición
	for (int i = 0; i < n; i++) { critical_points.push_back({x[i], 1, 0, 0}); }
 
	// Ordenar la lista que contiene tanto los árboles como los intervalos
	sort(critical_points.begin(), critical_points.end());
 
	priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
 
	int ans = 0;
 
	// Procesar todos los puntos críticos
	for (auto point : critical_points) {
		int type = point[1];
 
		if (type == 0) {
			// Procesamiento de intervalo
			int right = point[2];
			int amt_trees = point[3];
 
			pq.push({ans + amt_trees, right});
		} else {
			// Procesamiento de árbol
			int tree_position = point[0];
			while (!pq.empty() and (pq.top())[1] < tree_position) pq.pop();
 
			if (pq.empty() or (pq.top())[0] != ans) ans++;
		}
	}
 
	cout << ans << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int t;
	cin >> t;
	while (t--) { solve(); }
}


import sys
 
input = sys.stdin.readline
import heapq
import bisect
 
 
def solve():
	n, k = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
 
	critical_points = []
 
	# Procesar intervalos e insertarlos en la lista de puntos críticos, usando sus cotas derecha e izquierda, y la cantidad de árboles del intervalo menos la restricción
	for _ in range(k):
		left, right, t = map(int, input().split())
		right_amt = bisect.bisect_right(x, right)
		left_amt = bisect.bisect_left(x, left)
		critical_points.append([left, 0, right, (right_amt - left_amt) - t])
 
	# Añadir árboles a la lista de puntos críticos usando su posición
	for i in range(n):
		critical_points.append([x[i], 1, 0, 0])
 
	# Ordenar todos los puntos críticos
	critical_points.sort()
 
	pq = []  # min-heap
	ans = 0
 
	# Procesar todos los puntos críticos
	for point in critical_points:
		type_ = point[1]
 
		if type_ == 0:
			# Procesar intervalo
			right = point[2]
			amt_trees = point[3]
			heapq.heappush(pq, (ans + amt_trees, right))
		else:
			# Procesar un árbol
			tree_position = point[0]
 
			while pq and pq[0][1] < tree_position:
				heapq.heappop(pq)
 
			if not pq or pq[0][0] != ans:
				ans += 1
 
	print(ans)
 
 
def main():
	t = int(input())
	for _ in range(t):
		solve()
 
 
if __name__ == "__main__":
	main()