Skip to Content
CTRL K

Counting Liars

Análisis oficial (Java) 

Explicación

Después de ordenar la entrada, una observación importante es que si Bessie está en la posición xx, entonces la cantidad de vacas que mienten son todas las vacas con posición menor que xx que dicen “L” más todas las vacas con posición mayor que xx que dicen “G”.

Con esto, podemos recorrer la posición de cada vaca y calcular el total de mentirosas usando un bucle hacia adelante y un bucle hacia atrás.

La respuesta es el mínimo de mentirosas sobre todas las posiciones que recorremos.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
 
	vector<pair<int, char>> cows(n);
	for (int i = 0; i < n; i++) {
		// La posición se lee en .first para ordenar.
		cin >> cows[i].second >> cows[i].first;
	}
 
	sort(cows.begin(), cows.end());
 
	// lying_left[i] guarda la cantidad de vacas a la izquierda de la vaca i
	// que deben estar mintiendo dado que Bessie está en la posición de la vaca i.
	vector<int> lying_left(n);
	for (int i = 1; i < n; i++) {
		// Sumar todas las vacas que mienten a la izquierda de nuestra posición.
		lying_left[i] += lying_left[i - 1];
 
		if (cows[i - 1].second == 'L') {
			/*
			 * Si la vaca anterior dice que nuestra posición está a la izquierda
			 * pero su posición es estrictamente menor o igual que nuestra
			 * posición, está mintiendo.
			 */
			lying_left[i]++;
		}
	}
 
	// lying_right guarda lo mismo, pero para las vacas
	// a la *derecha* de i.
	vector<int> lying_right(n);
	// Lo llenamos de forma muy similar.
	for (int i = n - 2; i >= 0; i--) {
		lying_right[i] += lying_right[i + 1];
 
		if (cows[i + 1].second == 'G') { lying_right[i]++; }
	}
 
	int min_liars = n;
	for (int i = 0; i < n; i++) {
		min_liars = min(min_liars, lying_left[i] + lying_right[i]);
	}
 
	cout << min_liars << endl;
}
import java.io.*;
import java.util.*;
 
public class CountingLiars {
	// BeginCodeSnip{Cow Class}
	static class Cow implements Comparable<Cow> {
		char statement;
		int pos;
 
		public Cow(char statement, int pos) {
			this.statement = statement;
			this.pos = pos;
		}
 
		@Override
		public int compareTo(Cow c) {
			if (pos != c.pos) { return pos - c.pos; }
			return statement - c.statement;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(read.readLine());
 
		Cow[] cows = new Cow[n];
		for (int i = 0; i < n; i++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());
			cows[i] =
			    new Cow(cow.nextToken().charAt(0), Integer.parseInt(cow.nextToken()));
		}
		read.close();
 
		Arrays.sort(cows);
 
		// lying_left[i] guarda la cantidad de vacas a la izquierda de la vaca i
		// que deben estar mintiendo dado que Bessie está en la posición de la vaca i.
		int[] lying_left = new int[n];
		for (int i = 1; i < n; i++) {
			// Sumar todas las vacas que mienten a la izquierda de nuestra posición.
			lying_left[i] += lying_left[i - 1];
 
			if (cows[i - 1].statement == 'L') {
				/*
				 * Si la vaca anterior dice que nuestra posición está a la izquierda
				 * pero su posición es estrictamente menor que nuestra posición,
				 * está mintiendo.
				 */
				lying_left[i]++;
			}
		}
 
		// lying_right guarda lo mismo, pero para las vacas
		// a la *derecha* de i.
		int[] lying_right = new int[n];
		// Lo llenamos de forma muy similar.
		for (int i = n - 2; i >= 0; i--) {
			lying_right[i] += lying_right[i + 1];
 
			if (cows[i + 1].statement == 'G') { lying_right[i]++; }
		}
 
		int minLiars = n;
		for (int i = 0; i < n; i++) {
			minLiars = Math.min(minLiars, lying_left[i] + lying_right[i]);
		}
 
		System.out.println(minLiars);
	}
}
from typing import NamedTuple
 
 
class Cow(NamedTuple):
	pos: int
	statement: str
 
 
n = int(input())
cows = []
for _ in range(n):
	statement, pos = input().split()
	cows.append(Cow(int(pos), statement))
 
cows.sort(key=lambda c: (c.pos, c.statement))
 
# lying_left[i] guarda la cantidad de vacas a la izquierda de la vaca i
# que deben estar mintiendo dado que Bessie está en la posición de la vaca i.
lying_left = [0 for _ in range(n)]
for i in range(1, n):
	# Sumar todas las vacas que mienten a la izquierda de nuestra posición.
	lying_left[i] += lying_left[i - 1]
 
	if cows[i - 1].statement == "L":
		# Si la vaca anterior dice que nuestra posición está a la izquierda
		# pero su posición es estrictamente menor o igual que la nuestra, está mintiendo.
		lying_left[i] += 1
 
# lying_right guarda lo mismo, pero para las vacas
# a la *derecha* de i.
lying_right = [0 for _ in range(n)]
# Lo llenamos de forma muy similar.
for i in range(n - 2, -1, -1):
	lying_right[i] += lying_right[i + 1]
 
	if cows[i + 1].statement == "G":
		lying_right[i] += 1
 
min_liars = n
for i in range(n):
	min_liars = min(min_liars, lying_left[i] + lying_right[i])
 
print(min_liars)
Fundamentos