Drought

Explicación

Recorramos las vacas de izquierda a derecha, asegurándonos de que todas las vacas que ya procesamos tengan el mismo valor de hambre. Así, podemos partir este problema en casos:

Supongamos que las vacas están numeradas de $1$ a $n$ , y que estamos mirando la vaca $i$ . Si la vaca $i+1$ tiene un valor de hambre mayor, entonces basta con disminuir la vaca $i+1$ hasta el mismo valor de hambre que la vaca $i$ . Para ello elegimos el par de vacas $i+1$ e $i+2$ y disminuimos sus hambres hasta que la vaca $i+1$ tenga el mismo valor de hambre que la vaca $i$ . Por supuesto, si la vaca $i+2$ termina con un valor de hambre negativo, entonces es imposible y devolvemos $-1$ .

Ahora supongamos que la vaca $i$ tiene un valor de hambre mayor que la vaca $i+1$ . Obviamente no podemos disminuir más el hambre de la vaca $i+1$ porque nunca será igual: solo podemos disminuir el hambre de todas las vacas anteriores a $i+1$ . Para ello seleccionamos pares adyacentes de vacas empezando por las vacas de número impar y disminuimos juntos sus valores de hambre (vacas $1$ y $2$ , vacas $3$ y $4$ , $\ldots$ , vacas $i-1$ e $i$ ).

La siguiente secuencia de alimentación muestra cómo se puede aplicar esta estrategia:


5 5 5 5 3 ...
4 4 4 4 3 ...
3 3 3 3 3 ...

Después de esto, todas las vacas anteriores a $i+1$ habrán disminuido hasta el mismo valor de hambre que la vaca $i+1$ . Sin embargo, cuando $i$ es impar, es imposible disminuir su hambre a menos que también disminuyamos el valor de hambre de la vaca $i+1$ , así que devolvemos $-1$ .

Implementación

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

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
void solve() {
	int n;
	cin >> n;
	vector<ll> hunger(n + 1);  // hambre de cada vaca (indexación desde uno)
	for (int i = 1; i <= n; i++) { cin >> hunger[i]; }
 
	ll bags_needed = 0;
	for (int i = 1; i < n; i++) {
		if (hunger[i + 1] > hunger[i]) {
			if (i + 2 > n) {
				// Si la vaca i + 2 no existe, entonces no podemos
				// disminuir el par de vacas que empieza en i + 1.
				cout << -1 << "\n";
				return;
			}
 
			ll difference = hunger[i + 1] - hunger[i];
			hunger[i + 1] -= difference;
			hunger[i + 2] -= difference;
			if (hunger[i + 2] < 0) {
				// La vaca i + 2 no puede tener un valor de hambre negativo.
				cout << -1 << '\n';
				return;
			}
 
			// Se necesitan difference * 2 bolsas para llevar a las vacas i + 1 e i + 2
			// al nivel de la vaca i.
			bags_needed += difference * 2;
		} else if (hunger[i] > hunger[i + 1]) {
			if (i % 2 == 1) {
				// Si i es un índice impar, entonces es imposible.
				cout << -1 << "\n";
				return;
			}
 
			ll difference = hunger[i] - hunger[i + 1];
 
			// Se necesitan difference * i bolsas para llevar a todas las vacas
			// de 1 a i al mismo valor de hambre que la vaca i + 1.
			bags_needed += difference * i;
		}
	}
 
	cout << bags_needed << '\n';
}
 
int main() {
	int tests;
	cin >> tests;
	for (int t = 0; t < tests; t++) { solve(); }
}


import java.io.*;
import java.util.*;
 
public class Drought {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int n = io.nextInt();
 
			int[] hunger = new int[n + 1];  // hambre de cada vaca (indexación desde uno)
			for (int i = 1; i <= n; i++) { hunger[i] = io.nextInt(); }
 
			long bagsNeeded = 0;
			boolean ok = false;
			for (int i = 1; i < n; i++) {
				if (hunger[i + 1] > hunger[i]) {
					if (i + 2 > n) {
						// Si la vaca i + 2 no existe, entonces no podemos
						// disminuir el par de vacas que empieza en i + 1.
						ok = true;
						break;
					}
 
					long difference = hunger[i + 1] - hunger[i];
					hunger[i + 1] -= difference;
					hunger[i + 2] -= difference;
 
					if (hunger[i + 2] < 0) {
						// La vaca i + 2 no puede tener un valor de hambre negativo.
						ok = true;
						break;
					}
 
					// Se necesitan difference * 2 bolsas para llevar a las vacas i + 1 e i + 2
					// al nivel de la vaca i.
					bagsNeeded += difference * 2;
				} else if (hunger[i] > hunger[i + 1]) {
					if (i % 2 == 1) {
						// Si i es un índice impar, entonces es imposible.
						ok = true;
						break;
					}
 
					long difference = hunger[i] - hunger[i + 1];
 
					// Se necesitan difference * i bolsas para llevar a todas las vacas
					// de 1 a i al mismo valor de hambre que la vaca i + 1.
 
					bagsNeeded += difference * i;
				}
			}
 
			io.println((ok ? -1 : bagsNeeded));
		}
 
		io.close();
	}
 
	// CodeSnip{Kattio}
}


for _ in range(int(input())):
	n = int(input())
	hunger = list(map(int, input().split()))
	hunger = [0] + hunger
 
	bags_needed = 0
	ok = False
	for i in range(1, n):
		if hunger[i + 1] > hunger[i]:
			if i + 2 > n:
				# Si la vaca i + 2 no existe, entonces no podemos
				# disminuir el par de vacas que empieza en i + 1.
				ok = True
				break
 
			difference = hunger[i + 1] - hunger[i]
			hunger[i + 1] -= difference
			hunger[i + 2] -= difference
 
			if hunger[i + 2] < 0:
				# La vaca i + 2 no puede tener un valor de hambre negativo.
				ok = True
				break
 
			# Se necesitan difference * 2 bolsas para llevar a las vacas i + 1 e i + 2
			# al nivel de la vaca i.
			bags_needed += difference * 2
 
		elif hunger[i] > hunger[i + 1]:
			if i % 2 == 1:
				# Si i es un índice impar, entonces es imposible.
				ok = True
				break
 
		difference = hunger[i] - hunger[i + 1]
 
		# Se necesitan difference * i bolsas para llevar a todas las vacas
		# de 1 a i al mismo valor de hambre que la vaca i + 1.
		bags_needed += difference * i
 
	print(-1 if ok else bags_needed)