Secvența minimă cu sumă cel puțin S, în C++

În vectorul 2 3 1 2 4 3, cea mai scurtă secvență cu suma cel puțin 7 este 4 3, de lungime 2. Fereastra nu mai are lungime fixă: îi extindem capătul drept și îi restrângem capătul stâng cât timp suma rămâne suficientă.

Condiția esențială: valori pozitive

Citim 1≤n≤1000, ținta S cu 1≤S≤10^12 și n valori întregi între 1 și 10^9. Afișăm lungimea minimă sau 0 dacă nu există soluție. Nu acceptăm valori negative în această implementare. Adăugarea unui element în dreapta mărește suma, iar eliminarea unuia din stânga o micșorează.

Acest sens previzibil permite deplasarea frontierelor numai înainte. Dacă am admite negative, eliminarea unei valori negative ar mări suma, iar raționamentul ar trebui schimbat. O soluție nu devine generală doar pentru că citește într-un tip numeric cu semn.

Când înregistrăm un candidat

După adăugarea lui a[dr], dacă suma este cel puțin S, intervalul st..dr este valid. Înregistrăm lungimea lui înainte de a elimina a[st]. Repetăm eliminarea cât timp fereastra rămâne validă, pentru a găsi cea mai scurtă variantă cu același capăt drept.

Când suma cade sub S, o nouă eliminare nu ar putea ajuta, deoarece valorile sunt pozitive. Trebuie să avansăm capătul drept. Inițializăm best cu n+1, o lungime imposibilă pentru o secvență din vector.

În 2,3,1,2,4,3, ultimele două valori au suma 7. Nicio valoare singură nu ajunge la 7, deci lungimea minimă este 2.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n; long long tinta; cin >> n >> tinta;
    long long a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    int st=0,best=n+1; long long suma=0;
    for(int dr=0;dr<n;++dr) {
        suma+=a[dr];
        while(suma>=tinta) {
            if(dr-st+1<best) best=dr-st+1;
            suma-=a[st++];
        }
    }
    cout << (best==n+1?0:best) << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
using namespace std;
int main() {
    int n; long long tinta; cin >> n >> tinta;
    vector<long long> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    int st=0,best=n+1; long long suma=0;
    for(int dr=0;dr<n;++dr) {
        suma+=a[dr];
        while(suma>=tinta) {
            if(dr-st+1<best) best=dr-st+1;
            suma-=a[st++];
        }
    }
    cout << (best==n+1?0:best) << '\n';
}

De ce două bucle dau timp liniar

Capătul drept avansează exact n pași. Capătul stâng nu revine niciodată și poate avansa cel mult n pași în total, nu n pași pentru fiecare poziție a lui dr. Prin urmare timpul este O(n), deși există o buclă în interiorul alteia.

Fereastra goală are suma zero. Cum S este pozitiv, condiția buclei interioare devine falsă înainte de un acces la o poziție inexistentă. Schimbarea cerinței la S=0 ar necesita revizuirea acestei proprietăți și a sensului secvenței nevide.

Datele ocupă O(n) memorie; starea suplimentară are câteva variabile, O(1). În tabloul clasic capacitatea este 1000, iar n stabilește prefixul valid. Varianta vector păstrează aceleași limite și aceeași indexare de la zero.

Exersează

Exemplul 2 3 1 2 4 3, S=7 produce 2. Pentru 1 1, S=3, răspunsul este 0. Pentru 9 1 2, S=7, răspunsul este 1. Verifică și cazul în care numai întregul vector atinge ținta.

Continuă cu secvențele, sumele și analiza timpului.

Întrebări frecvente

Cum găsesc cea mai scurtă secvență cu suma cel puțin S?

Pentru valori strict pozitive, extinde fereastra la dreapta până când suma este suficientă, apoi restrânge-o din stânga cât timp condiția rămâne adevărată. Păstrează cea mai mică lungime întâlnită.

De ce sunt importante valorile pozitive pentru această fereastră?

Ele fac ca extinderea să crească suma și restrângerea să o micșoreze. Cu valori negative, aceste proprietăți dispar, iar aceeași regulă poate elimina soluții sau opri prea devreme căutarea.

Ce afișez dacă nicio secvență nu ajunge la suma S?

Lecția afișează 0 pentru absența soluției. Această valoare este un semnal convenit, nu lungimea unei secvențe valide cu sumă cel puțin S, deoarece S este pozitiv.