Skip to Content
CTRL K

Nusret Gökçe

Análisis oficial 

Explicación

La clave para resolver este problema es entender cómo suavizar la distribución de sal paso a paso.

Pensémoslo así:

  1. Avanzando (de izquierda a derecha), ninguna rebanada tiene demasiado poca sal comparada con la anterior. En concreto, cada rebanada debe tener al menos tanta sal como la anterior menos mm. Esto evita caídas bruscas de sabor.
  2. Retrocediendo (de derecha a izquierda), ninguna rebanada tiene demasiada sal comparada con la siguiente. Cada rebanada no debería superar el nivel de sal de la siguiente más mm. Esto evita picos repentinos al mirar hacia atrás.

Para lograrlo, partimos el problema en dos pasos:

  • Primero, recorremos de izquierda a derecha, asegurando que cada rebanada cumpla el mínimo según la anterior. Este paso se concentra en evitar zonas insípidas.
  • Luego, recorremos de derecha a izquierda, suavizando cualquier exceso de sal para que ninguna rebanada quede demasiado salada respecto de la siguiente. Este paso refina la distribución para equilibrarla.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <iostream>
#include <vector>
 
using std::cout;
using std::vector;
 
int main() {
	int n, m;
	std::cin >> n >> m;
	vector<int> arr(n);
	for (int &x : arr) { std::cin >> x; }
 
	int running_max = 0;
	for (int i = 0; i < n; i++) {
		running_max = std::max(arr[i], running_max - m);
		arr[i] = running_max;
	}
 
	running_max = 0;
	for (int i = n - 1; i >= 0; i--) {
		running_max = std::max(running_max - m, arr[i]);
		arr[i] = running_max;
	}
 
	for (int i = 0; i < n; i++) { cout << arr[i] << " \n"[i == n - 1]; }
}
import java.io.*;
import java.util.*;
 
public class NusretGokce {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }
 
		int runningMax = 0;
		for (int i = 0; i < n; i++) {
			runningMax = Math.max(arr[i], runningMax - m);
			arr[i] = runningMax;
		}
 
		runningMax = 0;
		for (int i = n - 1; i >= 0; i--) {
			runningMax = Math.max(runningMax - m, arr[i]);
			arr[i] = runningMax;
		}
 
		for (int i = 0; i < n; i++) {
			System.out.print(arr[i] + (i == n - 1 ? "\n" : " "));
		}
	}
}
n, m = map(int, input().split())
arr = list(map(int, input().split()))
 
running_max = 0
for i in range(n):
	running_max = max(arr[i], running_max - m)
	arr[i] = running_max
 
running_max = 0
for i in reversed(range(n)):
	running_max = max(arr[i], running_max - m)
	arr[i] = running_max
 
print(*arr)
Fundamentos