Skip to Content
CTRL K

Cyclic Array

Explicación

Podemos convertir esto en un problema de grafos, o más precisamente, un árbol. Agreguemos una arista de uu a vv si la longitud máxima del subarreglo que empieza en vv tiene que terminar en u−1u-1, y así el siguiente subarreglo debe empezar en uu. Recordemos que el arreglo es cíclico, así que uu no es necesariamente mayor que vv. Esto se puede encontrar usando dos punteros básicos. Podemos iterar por el arreglo con nuestro puntero izquierdo e incrementar nuestro puntero derecho si la suma entre los dos punteros es menor o igual que kk. Esto asegurará que el subarreglo que empieza en el puntero izquierdo sea lo más grande posible.

Podemos usar binary lifting para cada posición de inicio posible para determinar el número de saltos necesarios para cubrir exactamente nn elementos.

Implementación

Complejidad temporal: O(nlog⁡n)\mathcal O(n \log n)

#include <iostream>
 
const int MAX_N = 2e5 + 1;
const int LOG = 20;
 
/*
 * next[i][j] stores the start point of the next
 * 2^j'th subarray if we choose this subarray starting at i
 */
int nxt[2 * MAX_N][LOG];
 
int arr[2 * MAX_N];
 
int main() {
	int n;
	long long k;
	std::cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		std::cin >> arr[i];
		arr[i + n] = arr[i];
	}
 
	for (int i = 1, j = 1; i <= 2 * n; i++) {
		arr[i] += arr[i - 1];
		while (arr[i] - arr[j] > k) { j++; }
		nxt[i][0] = j;  // farthest position reachable from i
	}
 
	// binary lifting transition
	for (int j = 1; j < LOG; j++) {
		for (int i = 1; i <= 2 * n; i++) { nxt[i][j] = nxt[nxt[i][j - 1]][j - 1]; }
	}
 
	int res = n;
	for (int i = n; i <= 2 * n; i++) {
		int curr_res = 1;
		int pos = i;
 
		// using binary lifting to simulate jumps and cover 'n' elements
		for (int j = LOG - 1; j >= 0; j--) {
			if (nxt[pos][j] > i - n) {
				curr_res += (1 << j);
				pos = nxt[pos][j];
			}
		}
		res = std::min(res, curr_res);
	}
	std::cout << res << '\n';
}
MAX_N = 200001
LOG = 20
 
 
# next[i][j] stores the start point of the next
# 2^j'th subarray if we choose this subarray starting at i
nxt = [[0] * LOG for _ in range(2 * MAX_N)]
 
n, k = map(int, input().split())
arr = list(map(int, input().split()))
 
arr = [0] + arr + arr
 
j = 1
for i in range(1, 2 * n + 1):
	arr[i] += arr[i - 1]
	while arr[i] - arr[j] > k:
		j += 1
 
	nxt[i][0] = j  # farthest position reachable from i
 
# binary lifting transition
for j in range(1, LOG):
	for i in range(1, 2 * n + 1):
		nxt[i][j] = nxt[nxt[i][j - 1]][j - 1]
 
res = n
for i in range(n, 2 * n + 1):
	curr_res = 1
	pos = i
 
	# using binary lifting to simulate jumps and cover 'n' elements
	for j in range(LOG - 1, -1, -1):
		if nxt[pos][j] > i - n:
			curr_res += 1 << j
			pos = nxt[pos][j]
 
	res = min(res, curr_res)
 
print(res)
Fundamentos