• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Najdłuższy spójny ciąg o zadanej sumie

VPS Starter Arubacloud
0 głosów
508 wizyt
pytanie zadane 28 grudnia 2020 w C i C++ przez gryzedywany Użytkownik (510 p.)

Hejka 

Mam problem ze znalezieniem najdłuższego spójnego ciągu o zadanej sumie 

np. dla sumy 4 i ciągu 3 -2 6 1 -1 5 (ciąg -2 6 1 -1) 

Napisałam ten program ale sam kod ma złożoność n^2  (chyba) 

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,s;
    vector<int> v;
    cin>>n>>s;
    v.resize(n);
    int suma=0;
    for(int i=0; i<n;i++) 
    {
        cin>>v[i];
        suma=suma+v[i];
    }
    int templ=0, maxil=0;
    int temps=0;
    for(int i=0; i<n; i++){
        for(int j=i; j<n; j++){
           temps=temps+v[j], templ++;
           if(temps==s and templ>maxil) maxil=templ;
           //cout<<temps<<endl;
        }
        temps=0, templ=0;
    }
    if(maxil==0)cout<<"BRAK";
    else cout<<maxil;



}

Potrzebuję jednak czegoś o lepszej złożoności, myślałam o programowaniu dynamicznym jednak nie wiem jak się do tego zabrać. 

Dziękuję za wszystkie wskazówki <3 

2 odpowiedzi

0 głosów
odpowiedź 28 grudnia 2020 przez Whistleroosh Maniak (56,900 p.)
wybrane 28 grudnia 2020 przez gryzedywany
 
Najlepsza
Najlepiej to zrobić sumami prefiksowymi. Załóżmy, że suma[i] to suma prefiskowa pierwszych i elemntów ciągu. Dodatkowo powiedzmy, że najdłuższy spójny ciąg o danej sumie ma się kończyć na pozycji j. Wtedy szukamy takiej pozycji i (i < j), że suma[j] - suma[i] = zadana suma.

Musisz się jeszcze tylko zastanowić jak to zaimplementować.
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Masz podane jaki jest limit pamięci albo jakie są ograniczenia na n, s lub wartości ciągu?
komentarz 7 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
limit 32 mb

1<=n<=10^6

|s|<=10^6

elementy ciągu |x|<=10^6
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
To na pewno pom, para i mapa muszą być typu long long. Jeżeli to wciąż będzie za mało to spróbuj pozbyć się tablicy pom, bo ona jest tak naprawdę niepotrzebna
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Long long zajmie więcej, ale problem jest taki, że zwykły int może nie pomieścić wszystkich wartości. W najgorszym przypadku dostaniesz sumę prefisową równą 10^12, a int może przyjąć co najwyżej 10^9
komentarz 7 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
Faktycznie, rozumiem
0 głosów
odpowiedź 28 grudnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)
Musisz to zrobić gąsienicą. Trzymasz początek i koniec pewnego segmentu w tablicy  i pamiętasz jego sumę, jeżeli suma jest za mała to rozszerzasz okienko o kolejny element (przesuwasz koniec o jeden element do przodu), jeżeli za duża to przesuwasz początek o jeden element do przodu (zmniejszasz okienko)
2
komentarz 28 grudnia 2020 przez Whistleroosh Maniak (56,900 p.)
To może nie działać gdy elementy ciągu są ujemne
komentarz 28 grudnia 2020 przez jankustosz1 Nałogowiec (35,880 p.)
Rzeczywiście teraz zauważyłem, że przecież są ujemne

Podobne pytania

0 głosów
1 odpowiedź 1,408 wizyt
pytanie zadane 16 września 2018 w C i C++ przez jjanickij Użytkownik (510 p.)
0 głosów
3 odpowiedzi 706 wizyt
0 głosów
1 odpowiedź 733 wizyt
pytanie zadane 5 listopada 2016 w Algorytmy przez Wiciorny Ekspert (269,120 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...