Skip to Content
CTRL K

Set or Decrease

Análisis oficial (C++) 

Solución

Explicación

Usaremos búsqueda binaria para hallar el número mínimo de pasos necesarios, de modo que:

∑i=1nai≤k \sum_{i=1}^{n} a_i \leq k

Para ello, fijamos un punto medio m y comprobamos si podemos reducir la suma en al menos ∑i=1nai−k\sum_{i=1}^{n} a_i - k usando a lo sumo m operaciones.

La idea clave es que si gastamos algunas operaciones para decrementar el valor mínimo del arreglo y luego copiamos su valor a otros elementos, bajamos el valor de la suma total mucho más rápido que decrementando los elementos uno por uno.

Por lo tanto, para un m dado, partimos las operaciones en 2 partes:

  • decrementar el elemento mínimo en (m - i)
  • usar i operaciones para copiar el valor mínimo (i.e.,mn=arr[0]−(m−i))(i.e., mn = arr[0] - (m - i)) a ii otros elementos

Tras las operaciones anteriores, nuestro arreglo se verá más o menos así:

[mn, mn, …, mn⏟i elements∣arr[n−i], …, arr[n−1]⏟n−i elements] [\underbrace{mn,\ mn,\ \dots,\ mn}_{i \text{ elements}} \mid \underbrace{arr[n-i],\ \dots,\ arr[n-1]}_{n-i \text{ elements}}]

Ahora, para cada partición válida ii de 00 a min⁡(m,n−1)\min(m, n-1), devolvemos verdadero si podemos reducir la suma en al menos ∑i=1nai−k\sum_{i=1}^{n} a_i - k.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
	int test_cases;
	std::cin >> test_cases;
	while (test_cases--) {
 
		int n;
		long long k;
		std::cin >> n >> k;
		std::vector<int> arr(n);
		std::vector<long long> suffix_arr(n + 1);
		long long total = 0, res = 0;
 
		for (int &x : arr) {
			std::cin >> x;
			total += x;
		}
 
		if (total <= k) {
			std::cout << 0 << '\n';
			continue;
		}
 
		std::sort(begin(arr), end(arr));
 
		for (int i = n - 1; i >= 0; i--) { suffix_arr[i] = suffix_arr[i + 1] + arr[i]; }
 
		auto can = [&](long long mid) -> bool {
			for (int i = 0; i <= std::min(mid, (long long)n - 1); i++) {
				long long mn = arr[0] - (mid - i);
				// decrementar arr[0] en (mid - i) y reemplazar i elementos por él
				if (suffix_arr[n - i] - (mn * i) + (mid - i) >= total - k) {
					return true;
				}
			}
			return false;
		};
 
		long long lo = 0, hi = total - k;
		while (lo <= hi) {
			long long mid = (lo + hi + 1) >> 1;
			if (can(mid)) {
				hi = mid - 1;
				res = mid;
			} else {
				lo = mid + 1;
			}
		}
 
		std::cout << res << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class SetOrDecrease {
	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio();
 
		int testCases = io.nextInt();
		while (testCases-- > 0) {
			int n = io.nextInt();
			long k = io.nextLong();
			long total = 0;
			int[] arr = new int[n];
			long[] suffixArr = new long[n + 1];
			for (int i = 0; i < n; i++) {
				arr[i] = io.nextInt();
				total += arr[i];
			}
			if (total <= k) {
				io.println(0);
				continue;
			}
			Arrays.sort(arr);
			for (int i = n - 1; i >= 0; i--) {
				suffixArr[i] = suffixArr[i + 1] + arr[i];
			}
			long lo = 0, hi = total - k;
			long res = 0;
			while (lo <= hi) {
				long mid = (lo + hi + 1) / 2;
				if (can(mid, n, total, k, arr, suffixArr)) {
					hi = mid - 1;
					res = mid;
				} else {
					lo = mid + 1;
				}
			}
			io.println(res);
		}
		io.close();
	}
 
	static boolean can(long mid, int n, long total, long k, int[] arr,
	                   long[] suffixArr) {
		for (int i = 0; i <= Math.min(mid, (long)(n - 1)); i++) {
			long mn = arr[0] - (mid - i);
			// decrementar arr[0] en (mid - i) y reemplazar i elementos por él
			if (suffixArr[(int)(n - i)] - (mn * i) + (mid - i) >= total - k) {
				return true;
			}
		}
		return false;
	}
 
	// BeginCodeSnip{Kattio}
}
Fundamentos