Moamen and k-subarrays

Solución

Consideremos el número mínimo de subarreglos necesarios. Si este número es menor o igual que $k$ , entonces es resoluble usando $k$ subarreglos. Para hallar el número mínimo de subarreglos, podemos buscar una configuración de subarreglos donde el número de subarreglos sea mínimo. (Recordemos que los subarreglos deben ser contiguos) En concreto, en esta configuración, imaginemos un solo subarreglo. El orden de los elementos dentro del subarreglo nunca cambia, así que el orden de los elementos dentro del subarreglo es el mismo antes y después de reordenar los subarreglos. Esto significa que si conocemos de antemano el orden de los elementos ordenados, podemos aplicar un algoritmo voraz que intenta maximizar el tamaño del subarreglo anterior.

Por ejemplo, en el primer caso de prueba, el orden de los elementos es así:

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Tras ordenar, la lista queda así:

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	1	2	3	4	6

Luego podemos crear un mapa que asocie cada elemento al elemento que debería estar antes de él:

valor	1	2	3	4	6
$\texttt{map}[\texttt{value}]$	$\infty$	1	2	3	4

Con este mapa en mente, generamos los subconjuntos como se muestra:

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Índice:	0	1	2	3	4
$\texttt{arr}[i]$	6	3	4	2	1

Así, necesitamos 4 subarreglos como mínimo.

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

Demostración de la complejidad temporal

El ordenamiento requiere $\mathcal{O}(N\log N)$ , y las inserciones repetidas en el mapa también requieren $\mathcal{O}(N\log N)$ . Por lo tanto, la complejidad temporal total es $\mathcal{O}(N\log N)$ .

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
void solve() {
	int n, k;
	cin >> n >> k;
	int arr[(int)1e5 + 5];
	int sarr[(int)1e5 + 5];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sarr[i] = arr[i];
	}
	// Mapa de un valor al valor que le sigue en el arreglo ordenado
	map<int, int> next;
	sort(sarr, sarr + n);
	for (int i = 0; i < n - 1; i++) { next[sarr[i]] = sarr[i + 1]; }
	next[sarr[n - 1]] = INT32_MAX;  // Número ridículamente grande
	int ans = 1;
 
	// Si el elemento anterior en el arreglo desordenado no es el mismo
	// que el elemento anterior en el arreglo ordenado, necesitamos al menos 1 segmento
	// más
	for (int i = 1; i < n; i++) {
		if (next[arr[i - 1]] != arr[i]) ans++;
	}
	cout << (ans <= k ? "YES" : "NO") << endl;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--) solve();
}


import java.io.*;
import java.util.*;
 
public class MoamenSubarrays {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(f.readLine());
 
		int testNum = Integer.parseInt(st.nextToken());
		for (int t = 0; t < testNum; t++) {
			st = new StringTokenizer(f.readLine());
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
 
			int[] arr = new int[n];
			int[] sarr = new int[n];
 
			st = new StringTokenizer(f.readLine());
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				sarr[i] = arr[i];
			}
			Arrays.sort(sarr);
 
			// Mapa de un valor al valor que le sigue en el arreglo ordenado
			TreeMap<Integer, Integer> next = new TreeMap<>();
			for (int i = 0; i < n - 1; i++) { next.put(sarr[i], sarr[i + 1]); }
			next.put(sarr[n - 1], Integer.MAX_VALUE);
 
			int ans = 1;
			// Si el elemento anterior en el arreglo desordenado no es el mismo
			// que el elemento anterior en el arreglo ordenado, necesitamos al menos 1
			// segmento más
			for (int i = 1; i < n; i++) {
 
				if (next.get(arr[i - 1]) != arr[i]) ans++;
			}
			System.out.println(ans <= k ? "YES" : "NO");
		}
	}
}


for _ in range(int(input())):
	n, k = map(int, input().split())
	arr = list(map(int, input().split()))
 
	sarr = arr.copy()
	sarr.sort()
 
	after = {}  # Mapa (dict) de un valor al valor que le sigue en el arreglo ordenado
	for i in range(n - 1):
		after[sarr[i]] = sarr[i + 1]
 
	after[sarr[n - 1]] = float("inf")
	ans = 1
	for i in range(1, n):
		if after[arr[i - 1]] != arr[i]:
			# Si el elemento anterior en el arreglo desordenado no es el mismo
			# que el elemento anterior en el arreglo ordenado, necesitamos al menos 1 segmento más
			ans += 1
 
	print("YES" if ans <= k else "NO")