Skip to Content
CTRL K

Watching Mooloo

Análisis oficial (C++, Java, Python) 

Explicación

Resolvemos este problema con un algoritmo voraz.

Primero recorremos todos los días. El primer día, Bessie siempre tendrá que comprar una suscripción nueva. Sin embargo, en los días posteriores hay dos casos:

  1. Es mejor extender la última suscripción. Esto ocurre cuando el costo de extender la última suscripción, calculado restando la fecha de la última al día actual, es menor que KK.
  2. Si no se cumple la condición anterior, es mejor empezar una suscripción nueva por completo.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	int k;
	cin >> n >> k;
 
	vector<long long> days(n);
	for (long long &d : days) { cin >> d; }
 
	long long last_day = days[0];
	long long cost = k + 1;  // Empezar la primera suscripción
	for (long long d : days) {
		// ¿Debería Bessie extender la suscripción más reciente?
		if (d - last_day < k + 1) {
			cost += d - last_day;
		} else {
			// ¿O empezar una nueva por completo?
			cost += k + 1;
		}
 
		// Guardar la fecha de la última suscripción
		last_day = d;
	}
 
	cout << cost << endl;
}
import java.io.*;
import java.util.*;
 
public class WatchingMooloo {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);
 
		long[] days = new long[n];
		String[] daysInput = br.readLine().split(" ");
		br.close();
		for (int i = 0; i < n; i++) { days[i] = Long.parseLong(daysInput[i]); }
 
		long lastDay = days[0];
		long cost = k + 1;  // Empezar la primera suscripción
		for (long d : days) {
			// ¿Debería Bessie extender la suscripción más reciente?
			if (d - lastDay < k + 1) {
				cost += d - lastDay;
			} else {
				// ¿O empezar una nueva por completo?
				cost += k + 1;
			}
 
			// Guardar la fecha de la última suscripción
			lastDay = d;
		}
 
		System.out.println(cost);
	}
}
n, k = map(int, input().split())
days = list(map(int, input().split()))
 
last_day = days[0]
cost = k + 1  # Empezar la primera suscripción
 
for d in days:
	# ¿Debería Bessie extender la suscripción más reciente?
	if d - last_day < k + 1:
		cost += d - last_day
	else:
		# ¿O empezar una nueva por completo?
		cost += k + 1
 
	# Guardar la fecha de la última suscripción
	last_day = d
 
print(cost)
Fundamentos