Skip to Content
CTRL K

Diamond Collector

Análisis oficial (Java) 

Solución

Explicación

Primero ordenamos los diamantes por tamaño, lo que nos permite considerar grupos de diamantes en orden. Para cada diamante, determinamos la cantidad máxima de diamantes que se pueden agrupar con él sin exceder la diferencia de tamaño permitida.

Precomputamos el mejor agrupamiento posible desde cada punto de partida de modo que, una vez que fijamos un grupo para un estuche, podamos identificar rápidamente el grupo óptimo para el segundo estuche a partir de los diamantes restantes más grandes.

Finalmente, combinamos los dos grupos para determinar la cantidad total máxima de diamantes que se pueden exhibir en ambos estuches.

Implementación

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

#include <algorithm>
#include <fstream>
#include <iostream>
 
int main() {
	std::ifstream cin("diamond.in");
 
	int n, k;
	cin >> n >> k;
	int arr[n];
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
 
	std::sort(arr, arr + n);
 
	// cuántos diamantes podemos tomar
	// asumiendo que i es el diamante más a la izquierda
	int can_take_left[n];
	int l = 0, r = 0;
	for (; l < n; l++) {
		while (r < n && arr[r] - arr[l] <= k) r++;
		can_take_left[l] = r - l;
	}
 
	// max_val_after_i[i] = valor máximo de can_take_left[x] para algún x >= i.
	int max_val_after_i[n + 1];
	max_val_after_i[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		max_val_after_i[i] = std::max(max_val_after_i[i + 1], can_take_left[i]);
	}
 
	int ans = 0;
	for (int l = 0; l < n; l++) {
		ans = std::max(ans, can_take_left[l] + max_val_after_i[l + can_take_left[l]]);
	}
 
	std::ofstream("diamond.out") << ans << std::endl;
}

Fuente: Nick Wu, del editorial oficial de USACO

import java.io.*;
import java.util.*;
public class diamondS {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("diamond.in"));
		PrintWriter pw =
		    new PrintWriter(new BufferedWriter(new FileWriter("diamond.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[] list = new int[n];
		for (int i = 0; i < n; i++) { list[i] = Integer.parseInt(br.readLine()); }
		Arrays.sort(list);
		// leftmostIndex[i] guarda el índice del diamante más pequeño que se puede
		// incluir dado que el diamante más grande del estuche tiene tamaño list[i].
		int[] leftmostIndex = getLeftmost(list, k);
		// leftSize[i] guarda la cantidad máxima de diamantes dado que todos
		// los diamantes tienen tamaño a lo sumo list[i].
		int[] leftSize = new int[n];
		for (int i = 0; i < n; i++) {
			leftSize[i] = i - leftmostIndex[i] + 1;
			if (i > 0) { leftSize[i] = Math.max(leftSize[i], leftSize[i - 1]); }
		}
		// rightmostIndex[i] guarda el índice del diamante más pequeño que se
		// puede incluir dado que el diamante más pequeño del estuche tiene tamaño
		// list[i].
		int[] rightmostIndex = getRightmost(list, k);
		// leftSize[i] guarda la cantidad máxima de diamantes dado que todos
		// los diamantes tienen tamaño al menos list[i].
		int[] rightSize = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			rightSize[i] = rightmostIndex[i] - i + 1;
			if (i < n - 1) { rightSize[i] = Math.max(rightSize[i], rightSize[i + 1]); }
		}
		int ret = 0;
		for (int i = 0; i < n - 1; i++) {
			ret = Math.max(ret, leftSize[i] + rightSize[i + 1]);
		}
		pw.println(ret);
		pw.close();
	}
 
	public static int[] getRightmost(int[] list, int k) {
		int[] ret = new int[list.length];
		int j = list.length - 1;
		for (int i = list.length - 1; i >= 0; i--) {
			while (j >= 0 && list[j] - list[i] > k) { j--; }
			ret[i] = j;
		}
		return ret;
	}
 
	public static int[] getLeftmost(int[] list, int k) {
		int[] ret = new int[list.length];
		int j = 0;
		for (int i = 0; i < list.length; i++) {
			while (j < list.length && list[i] - list[j] > k) { j++; }
			ret[i] = j;
		}
		return ret;
	}
}
import sys
 
sys.stdin = open("diamond.in", "r")
sys.stdout = open("diamond.out", "w")
 
n, k = map(int, input().split())
arr = sorted([int(input()) for i in range(n)])
 
# cantidad máxima de diamantes asumiendo que i es el diamante más pequeño
max_diamond = [0] * (n + 1)
j = 0
for i in range(n):
	while j < n and arr[j] - arr[i] <= k:
		j += 1
	j -= 1
	max_diamond[i] = j - i + 1
 
suffix_max = [0 for i in range(n + 1)]  # máximo de sufijos
suffix_max[n - 1] = max_diamond[n - 1]
for i in range(n - 2, -1, -1):
	suffix_max[i] = max(max_diamond[i], suffix_max[i + 1])
 
ans = 0
for i in range(n):
	ans = max(ans, max_diamond[i] + suffix_max[i + max_diamond[i]])
 
print(ans)
Fundamentos