Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Okno przesuwne dla nieujemnych wartości

Okno przesuwne utrzymuje spójny fragment tablicy i przesuwa jego granice bez ponownego sumowania wszystkich elementów. Wariant z kurczeniem okna wymaga nieujemnych danych.

Wersja: C23; repository compiler flag, production runtime not attested

Składnia

Use this shrinking-window rule only when all input values are nonnegative and the target is strictly positive. Use a running-sum type that can represent every intermediate sum without overflow, including the sum immediately after adding an element and before shrinking the window. Maintain left and right window boundaries and add each entering value to the running sum. While the current sum is at least the target, compare the current window length with the shortest found so far and update it if needed. Then subtract the leftmost value and advance the left boundary, even if that removal drops the sum below the target. An empty window has sum zero, so the positive target ensures that the loop stops before attempting to remove another element.

Okno przesuwne opisują dwa indeksy: lewy i prawy. Prawa granica dołącza kolejny element do sumy. Gdy suma osiąga próg, lewa granica przesuwa się w prawo, a usuwane wartości są odejmowane. Każdy element wchodzi do okna i opuszcza je najwyżej raz, dlatego przejście ma liniową złożoność czasową.

Warunek nieujemności jest istotny. Po dodaniu liczby nieujemnej suma nie maleje, a po usunięciu jej z lewej strony nie rośnie. Ta monotoniczność pozwala bezpiecznie zawężać okno. Dla liczb ujemnych takie rozumowanie przestaje działać i potrzebny jest inny algorytm.

Przykład szuka najkrótszego spójnego fragmentu o sumie co najmniej 7. Dla danych 2, 1, 5, 2, 3, 2 wynikiem jest długość 2, ponieważ fragment 5, 2 spełnia warunek.

Przykłady

#include <stddef.h>
#include <stdio.h>

int main(void) {
    const int values[] = {2, 1, 5, 2, 3, 2};
    const size_t count = sizeof values / sizeof values[0];
    const int target = 7;
    size_t left = 0;
    size_t best = count + 1;
    int sum = 0;

    for (size_t right = 0; right < count; ++right) {
        sum += values[right];
        while (sum >= target) {
            const size_t length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left++];
        }
    }

    if (best == count + 1) printf("none\n");
    else printf("%zu\n", best);
    return 0;
}

Wynik

2

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła