Skip to Content
CTRL K

To Become Max

Editorial oficial (C++) 

Explicación

Iteramos por todos los elementos y hacemos búsqueda binaria sobre el mayor valor al que podemos llevarlos.

Digamos que queremos incrementar aia_i hasta xx. Para ello, necesitamos lo siguiente:

  • ai+1a_{i+1} al menos x−1x-1
  • ai+2a_{i+2} al menos x−2x-2
  • y así sucesivamente…

Conviene probar con algunos ejemplos chicos para ver por qué esto es cierto.

Hay dos desenlaces posibles.

  1. Llegamos a un punto donde ai+na_{i+n} ya es al menos x−nx-n. En ese momento podemos dejar de buscar y calcular el número total de operaciones.
  2. Llegamos al último elemento y resulta que necesitamos que sea mayor que su valor actual, lo cual es imposible.

Mientras no ocurra el segundo escenario y el número total de operaciones sea menor que el máximo que nos dieron, todo está bien.

Implementación

Complejidad temporal: O(n2log⁡k)\mathcal{O}(n^2 \log k)

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int len;
		int max_ops;
		std::cin >> len >> max_ops;
		vector<int> arr(len);
		for (int &i : arr) { std::cin >> i; }
 
		int best = INT32_MIN;
		for (int start = 0; start < len; start++) {
			int lo = arr[start];
			int hi = arr[start] + max_ops;
			int doable = -1;
			while (lo <= hi) {
				int mid = (lo + hi) / 2;
 
				long long needed = 0;
				for (int i = start; i < len; i++) {
					int diff = mid - (i - start) - arr[i];
					if (diff <= 0) { break; }
					if (i == len - 1) {
						needed = INT64_MAX;
						break;
					}
					needed += diff;
				}
 
				if (needed <= max_ops) {
					doable = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
 
			best = std::max(best, doable);
		}
 
		cout << best << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class ToBecomeMax {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer initial = new StringTokenizer(read.readLine());
			int len = Integer.parseInt(initial.nextToken());
			int maxOps = Integer.parseInt(initial.nextToken());
			int[] arr = Arrays.stream(read.readLine().split(" "))
			                .mapToInt(Integer::parseInt)
			                .toArray();
 
			int best = Integer.MIN_VALUE;
			// recorremos todos los elementos de partida
			for (int start = 0; start < len; start++) {
				int lo = arr[start];
				int hi = arr[start] + maxOps;
				int doable = -1;
 
				// y hacemos búsqueda binaria sobre el mayor valor que pueden alcanzar
				while (lo <= hi) {
					int mid = (lo + hi) / 2;
 
					long needed = 0;
					for (int i = start; i < len; i++) {
						int diff = mid - (i - start) - arr[i];
						if (diff <= 0) {
							break;  // por suerte, podemos parar ahora
						}
						// hay que incrementar el último elemento para que este máximo funcione
						// lo cual es imposible
						if (i == len - 1) {
							needed = Long.MAX_VALUE;
							break;
						}
						needed += diff;
					}
 
					if (needed <= maxOps) {
						doable = mid;
						lo = mid + 1;
					} else {
						hi = mid - 1;
					}
				}
 
				best = Math.max(best, doable);
			}
 
			System.out.println(best);
		}
	}
}
for _ in range(int(input())):
	len_, max_ops = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
 
	best = -float("inf")
	for start in range(len_):
		lo = arr[start]
		hi = arr[start] + max_ops
		doable = -1
		while lo <= hi:
			mid = (lo + hi) // 2
 
			needed = 0
			for i in range(start, len_):
				diff = mid - (i - start) - arr[i]
				if diff <= 0:
					break
				if i == len_ - 1:
					needed = float("inf")
					break
				needed += diff
 
			if needed <= max_ops:
				doable = mid
				lo = mid + 1
			else:
				hi = mid - 1
 
		best = max(best, doable)
 
	print(best)
Fundamentos