• 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 28 grudnia 2020 przez gryzedywany Użytkownik (510 p.)
Jejku faktycznie, głupia jestem, że na to nie wpadłam. Wielkie dzięki <3
komentarz 1 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
Hej jednak nie wychodzi mi implementacja tak żeby znajdować i lub j w krótszym czasie :/ nie mam pomysłu jak się do tego zabrać żeby to dzialało szybciej niż to co miałam wcześniej
komentarz 1 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Możesz iterowac się po j oraz na bieżąco liczyć sumę prefiksową od pozycji 0 do j. Teraz z tego równania suma[j] - suma [i] = szukana suma wyznaczasz sobie suma[i] = suma[j] - szukana suma. I w ogóle w mapie możesz trzymać dla każdej wartości sumy prefiskowej na jakiej najwcześniejszej pozycji ta suma występowała. Czyli sprawdzasz czy w mapie masz wartość suma[i], jeżeli tak to znasz pozycję i, jeżeli nie to nie istnieje takie i. Potem tylko dodajesz do mapy suma[j] i zwiekszasz j o 1 i robisz to samo
komentarz 5 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
Masz na myśli użycie kontenera mapy i funkcji find?
komentarz 5 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Tak
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Jest w miarę dobrze tylko pierwszy element tablicy pom musi być równy 0 i to co robisz w drugiej pętli musisz wstawić do pierwszej pętli, bo jak jesteś na pozycji i to musisz rozważyć wszystkie sumy prefiksowe tylko dla prefiksu długości co najwyzej i
komentarz 7 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
Niestety to nie naprawiło problemu  z pamięcią i nadal w jednym teście zwraca zły wynik. Zauważyłam też, że np dla danych:

5 (elementów) 5 (szukana suma)

-5 5 -5 5 5 (ciąg)

algorytm zwraca zły wynik
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
To jakbyś mogła pokazać ten nowszy kod
komentarz 7 stycznia 2021 przez Whistleroosh Maniak (56,900 p.)
Przed pętlą musisz jeszcze dodać {0, 0} do mapy. Wstawiaj parę do mapy pod sam koniec petli. I jeszcze brakuje tu jakiegoś pom.resize, mimo iż w poprzednim kodzie był
komentarz 7 stycznia 2021 przez gryzedywany Użytkownik (510 p.)
Faktycznie teraz zwraca dobry wynik ale nadal przekracza limit pamięci
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,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 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!

...