Skip to Content
CTRL K

Building an Aquarium

Editorial oficial (C++) 

Explicación

Hacemos búsqueda binaria sobre el mayor valor hh que usa a lo sumo xx unidades de agua. La cantidad de agua usada crece de forma monótona con la altura: cuanto más alto es el tanque, más agua hace falta para llenarlo.

Para hallar la cantidad de agua usada, sumamos los valores de max(h−ai,0) ∀i∈n\text{max}(h-a_i, 0) \ \forall i\in n. h−aih-a_i representa las unidades de agua por encima del coral ii, porque h−aih-a_i es el espacio vacío que hay que llenar con agua (ver el dibujo del enunciado si no queda claro). El 00 aparece si h<aih<a_i, es decir, si el coral es más alto que el tanque. Como dice el enunciado, en ese caso no se debe agregar agua por encima de ese coral.

La búsqueda binaria se hace en [0,amax+x][0,a_\text{max}+x], donde amaxa_\text{max} es el coral más alto.

Implementación

Complejidad temporal: O(nlog⁡(amax+x))\mathcal{O}(n\log\left(a_\text{max}+x\right)) por caso de prueba

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
	int n, x;
	cin >> n >> x;
 
	vector<int> corals(n);
	int maxCoral = 0;
 
	for (int &coral : corals) {
		cin >> coral;
 
		if (coral > maxCoral) { maxCoral = coral; }
	}
 
	// definimos los extremos de la búsqueda binaria
	ll l = 0, r = maxCoral + x;
 
	while (l < r) {
		ll h = l + (r - l + 1) / 2;
 
		// calculamos el agua usada
		ll waterUsed = 0;
 
		for (int &coral : corals) { waterUsed += max(h - coral, (ll)0); }
 
		if (waterUsed > x) {
			r = h - 1;
		} else {
			l = h;
		}
	}
 
	cout << l << "\n";
}
 
int main() {
	int t;
	cin >> t;
 
	while (t--) { solve(); }
}
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class BuildingAquarium {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int t = Integer.parseInt(st.nextToken());
 
		while (t-- > 0) {
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
 
			List<Integer> corals = new ArrayList<>();
			int maxCoral = 0;
 
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < n; i++) {
				int coral = Integer.parseInt(st.nextToken());
 
				corals.add(coral);
 
				if (coral > maxCoral) { maxCoral = coral; }
			}
 
			// definimos los extremos de la búsqueda binaria
			long l = 0, r = maxCoral + x;
 
			while (l < r) {
				long h = l + (r - l + 1) / 2;
 
				// calculamos el agua usada
				long waterUsed = 0;
 
				for (int coral : corals) { waterUsed += Math.max(h - coral, 0); }
 
				if (waterUsed > x) {
					r = h - 1;
				} else {
					l = h;
				}
			}
 
			System.out.println(l);
		}
	}
}
def solve():
	n, x = map(int, input().split())
	corals = list(map(int, input().split()))
 
	maxCoral = corals[0]
 
	for coral in corals:
		if coral > maxCoral:
			maxCoral = coral
 
	# definimos los extremos de la búsqueda binaria
	l = 0
	r = maxCoral + x
 
	while l < r:
		h = int(l + (r - l + 1) / 2)
 
		# calculamos el agua usada
		waterUsed = 0
 
		for coral in corals:
			waterUsed += max(h - coral, 0)
 
		if waterUsed > x:
			r = h - 1
		else:
			l = h
 
	print(l)
 
 
t = int(input())
 
for _ in range(t):
	solve()
Fundamentos