Out of Place

Solución en video

Por Vikas Thoutam

Código de la solución en video

C++Java


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// entrada y salida por archivos
	freopen("outofplace.in", "r", stdin);
	freopen("outofplace.out", "w", stdout);
 
	// Leemos el tamaño del arreglo (n) y creamos el arreglo original y el ordenado,
	// además de la variable de diferencias
	int n;
	cin >> n;
	int og[n];
	int sorted[n];
	int diff = 0;
 
	// Leemos los valores del arreglo como entrada
	// y los colocamos tanto en original como en sorted
	for (int i = 0; i < n; i++) {
		cin >> og[i];
		sorted[i] = og[i];
	}
 
	// Ordenamos de verdad el arreglo "sorted"
	sort(sorted, sorted + n);
 
	// Contamos la cantidad de diferencias entre los arreglos
	for (int i = 0; i < n; i++) {
		if (og[i] != sorted[i]) { diff++; }
	}
 
	// Imprimimos 0 si no hay diferencias (ningún swap) o
	// diff - 1 si hay diferencias
	cout << max(0, diff - 1);
 
	return 0;
}


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
public class OutofPlace {
	public static void main(String[] args) throws IOException {
		// Entrada y salida por archivos
		BufferedReader br = new BufferedReader(new FileReader("outofplace.in"));
		PrintWriter pw = new PrintWriter("outofplace.out");
 
		// Leemos el tamaño del arreglo (n) y creamos el arreglo original y el ordenado,
		// además de la variable de diferencias
		int n = Integer.parseInt(br.readLine());
		int[] og = new int[n];
		int[] sort = new int[n];
		int diff = 0;
 
		// Leemos los valores del arreglo como entrada
		// y los colocamos tanto en original como en sorted, en el mismo orden
		for (int i = 0; i < n; i++) {
			og[i] = Integer.parseInt(br.readLine());
			sort[i] = og[i];
		}
 
		// Ordenamos de verdad el arreglo "sorted"
		Arrays.sort(sort);
 
		// Calculamos la cantidad de posiciones que son
		// distintas entre los arreglos og y sorted
		for (int i = 0; i < n; i++) {
			if (og[i] != sort[i]) { diff++; }
		}
 
		// Imprimimos 0 si no hay diferencias (ningún swap) o diff - 1. Si hay
		// diferencias (hace falta un swap por cada diferencia, menos 1)
		pw.println(Math.max(0, diff - 1));
		pw.close();
	}
}

Explicación

Partimos de la lista de $N$ alturas y hacemos una copia ordenada. Luego comparamos la lista original con la lista ordenada, llevando registro de en qué posiciones difieren.

Como quitar exactamente una vaca debe dejar la lista ordenada, esas $K$ vacas fuera de lugar forman una secuencia que está ordenada salvo por un elemento, así que hacen falta exactamente $K-1$ movimientos para volver a dejar a todas en orden (y si $K \le 1$ , no hace falta ningún movimiento).

Implementación

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

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	freopen("outofplace.in", "r", stdin);
	int cow_num;
	std::cin >> cow_num;
	vector<int> cows(cow_num);
	for (int &c : cows) { std::cin >> c; }
 
	vector<int> sorted_order(cows);
	std::sort(sorted_order.begin(), sorted_order.end());
 
	// La cantidad de vacas que están fuera de lugar respecto del orden ordenado
	int bad_num = 0;
	for (int i = 0; i < cow_num; i++) {
		if (cows[i] != sorted_order[i]) { bad_num++; }
	}
 
	freopen("outofplace.out", "w", stdout);
	cout << bad_num - 1 << endl;
}


import java.io.*;
import java.util.*;
 
public class OutOfPlace {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("outofplace.in"));
		int cowNum = Integer.parseInt(read.readLine());
		int[] cows = new int[cowNum];
		for (int c = 0; c < cowNum; c++) {
			cows[c] = Integer.parseInt(read.readLine());
		}
		read.close();
 
		int[] sortedOrder = cows.clone();
		Arrays.sort(sortedOrder);
 
		// La cantidad de vacas que están fuera de lugar respecto del orden ordenado
		int badNum = 0;
		for (int i = 0; i < cowNum; i++) {
			if (cows[i] != sortedOrder[i]) { badNum++; }
		}
 
		PrintWriter written = new PrintWriter("outofplace.out");
		written.println(badNum - 1);
		written.close();
	}
}


with open("outofplace.in") as read:
	cow_num = int(read.readline())
	cows = [int(read.readline()) for _ in range(cow_num)]
 
sorted_order = sorted(cows)
 
# La cantidad de vacas que están fuera de lugar respecto del orden ordenado
bad_num = 0
for i in range(len(cows)):
	if cows[i] != sorted_order[i]:
		bad_num += 1
 
print(bad_num - 1, file=open("outofplace.out", "w"))