• 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

0 głosów
184 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 Nałogowiec (30,620 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 Nałogowiec (30,620 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 Nałogowiec (30,620 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 Nałogowiec (30,620 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 (30,160 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 Nałogowiec (30,620 p.)
To może nie działać gdy elementy ciągu są ujemne
komentarz 28 grudnia 2020 przez jankustosz1 Nałogowiec (30,160 p.)
Rzeczywiście teraz zauważyłem, że przecież są ujemne

Podobne pytania

0 głosów
1 odpowiedź 551 wizyt
pytanie zadane 16 września 2018 w C i C++ przez jjanickij Użytkownik (510 p.)
0 głosów
3 odpowiedzi 405 wizyt
0 głosów
1 odpowiedź 492 wizyt
pytanie zadane 5 listopada 2016 w Algorytmy przez Wiciorny Mędrzec (198,200 p.)

86,512 zapytań

135,267 odpowiedzi

300,567 komentarzy

57,262 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...