Skip to Content
CTRL K

Sleepy Cow Sorting

Análisis oficial (C++) 

Solución

Explicación

Podemos pensar este problema mirando el final del arreglo de vacas.

Observemos que si los últimos ii elementos del arreglo están ordenados de forma creciente, FJ puede ordenar por completo a las vacas en n−in-i pasos de tiempo. Esto es porque los primeros n−in-i elementos todavía hay que ordenarlos.

Así, podemos encontrar la última vaca desordenada e imprimir su posición.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("sleepy.in", "r", stdin);
 
	int n;
	cin >> n;
	vector<int> cows(n);
	for (int &c : cows) { cin >> c; }
 
	int answer = n - 1;
	for (int i = n - 2; i >= 0; i--) {
		if (cows[i] < cows[i + 1]) {
			answer = i;
		} else {
			break;
		}
	}
 
	freopen("sleepy.out", "w", stdout);
	cout << answer << endl;
}
import java.io.*;
import java.util.*;
 
public class SleepyCowSorting {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("sleepy");
		int n = io.nextInt();
		int[] cows = new int[n];
 
		for (int i = 0; i < n; i++) { cows[i] = io.nextInt(); }
 
		// Encontramos la cantidad de valores estrictamente crecientes al final de la lista
		int answer = n - 1;
		for (int i = n - 2; i >= 0; i--) {
			if (cows[i] < cows[i + 1]) { answer = i; }
			break;
		}
 
		io.println(answer);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
file_in = open("sleepy.in")
data = file_in.read().strip().split("\n")
 
n = int(data[0])
cows = list(map(int, data[1].split(" ")))
 
ans = 0
# Encontramos la cantidad de valores estrictamente crecientes al final de la lista
for i in range(n - 1, 0, -1):
	if cows[i] < cows[i - 1]:
		ans = i
		break
 
print(ans, file=open("sleepy.out", "w"))

Solución en video

Por Vikas Thoutam

Video de YouTube (9sh0XJryLAg)

Código de la solución en video
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// Entrada y salida por archivos
	freopen("sleepy.in", "r", stdin);
	freopen("sleepy.out", "w", stdout);
 
	// Leemos el tamaño del arreglo (n) y creamos un arreglo para guardar las posiciones de las vacas
	int n;
	cin >> n;
	int cows[n];
 
	// Leemos las posiciones iniciales de las vacas y las guardamos en el arreglo
	for (int i = 0; i < n; i++) { cin >> cows[i]; }
 
	// Calculamos x, la longitud del subarreglo creciente al final
	int x = 1;
	for (int i = n - 2; i > -1 && cows[i] < cows[i + 1]; i--) x++;
 
	// Imprimimos la respuesta, n-x
	printf("%d", n - x);
	fclose(stdout);
}
import java.io.*;
import java.util.StringTokenizer;
 
public class SleepyCowSorting {
	public static void main(String[] args) throws IOException {
		// Entrada y salida por archivos
		BufferedReader br = new BufferedReader(new FileReader("sleepy.in"));
		PrintWriter pw = new PrintWriter("sleepy.out");
 
		// Leemos el tamaño del arreglo (n) y creamos un arreglo para guardar las
		// posiciones de las vacas
		int n = Integer.parseInt(br.readLine());
		int[] cows = new int[n];
 
		// Leemos las posiciones iniciales de las vacas y las guardamos en el arreglo
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) { cows[i] = Integer.parseInt(st.nextToken()); }
 
		// Calculamos x, la longitud del subarreglo creciente al final
		int x = 1;
		for (int i = n - 2; i > -1 && cows[i] < cows[i + 1]; i--) x++;
 
		// Imprimimos la respuesta, n-x
		pw.print(n - x);
		pw.close();
	}
}
Fundamentos