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

Zadanie z wyszukiwaniem binarnym po wyniku.

VPS Starter Arubacloud
+1 głos
497 wizyt
pytanie zadane 20 sierpnia 2017 w C i C++ przez maciek259 Nowicjusz (240 p.)

Witam bardzo serdecznie, mam problem z zadaniem wykorzystującym wyszukiwanie binarne. Napisany przeze mnie kod daje błędne wyniki w test case'ie. Proszę o wskazanie błędów, które popełniłem. 

Mamy daną tablicę n liczb całkowitych. Dla każdego elementu tej tablicy szukamy minimalnego promienia ri, takiego że suma wszystkich elementów oddalonych o maksymalnie ri od tego elementu jest równa lub większa od pewnej ustalonej wartości wi.

Wejście: Pierwszy wiersz wejścia zawiera liczbę n(1<= n <= 500 000) ozn. liczbę elem. tablicy. W drugim wierszu wejścia jest n liczb całkowitych t0,t1,t2,...tn-1(1<= t <= 1 000 000), gdzie ti ozn. wartość i-tego elementu tablicy, a w trzecim wierszu n licz całk w0, w1, w2,... wn-1 (1<= w<= 10^9), gdzie w ozn. ustaloną wartość dla i-tego elementu tablicy.

Wyjście: Pierwszy i jedyny wiersz wyjścia powinien zawierać  n liczb całkowitych r1,r2,r3...rn-1, gdzie ri jest minimalnym promieniem dla i-tego elementu, lub wartość -1, gdy nie można znaleźć odpowiedniego promienia.

Przykład:

 6

2 3 1 4 2 1                  

6 3 8 8 10 14

Poprawna odpowiedź:

2 0 1 2 3 -1

#include<cstdio>
#include<algorithm>
using namespace std;
/* test case
6
2 3 1 4 2 1
6 3 8 8 10 14

answer:
2 0 1 2 3 -1
*/
int t[1000006]; // wejscie
int w[1000006]; // wejscie

int sum[500001]; // tablica sum prefiksowych sum elementów
bool check(int x,int r,int n)
{
    if(sum[min(x+r,n)]-sum[max(x-r,0)]>=w[x])
   // if(sum[x+r]-sum[x-r]-t[x]>=w[x])
        return true;
    return false;
}
int bin(int a,int b)
{
    int r=0;
    int wynik=-1;
    int x=a;
    int n=b;

    while(b-a>1)
    {
        r=(a+b)/2;
        //printf("wynik:%d   a:%d   b:%d   \n",wynik,a,b);

        if(check(x,r,n))
            {
                wynik=r;
                b=r;
            }
        else
            a=r;
    }
    return wynik;

}
int main()
{
    int n;
    scanf("%d",&n);

    for(int i=0;i<n;++i)
        scanf("%d",&t[i]);

    sum[0]=t[0];

    for(int i=1;i<n;++i)
        sum[i]=sum[i-1]+t[i];

    for(int i=0;i<n;++i)
        scanf("%d",&w[i]);

    for(int i=0;i<n;++i)
       printf("%d\n",bin(i,n-1));

    return 0;
}

 

1 odpowiedź

0 głosów
odpowiedź 21 sierpnia 2017 przez d0n Mądrala (6,440 p.)
Hipotetyczna sytuacja: jeśli mamy tablice sum prefiksowych pref i potrzebujemy sumy od elementu a do b włącznie, to napiszemy pref[b] - pref[a - 1], u ciebie jest coś w stylu pref[b] - pref[a], czyli bez elementu tablica[a] ( linijka 18 u Ciebie w kodzie )

Podobne pytania

0 głosów
1 odpowiedź 778 wizyt
pytanie zadane 18 sierpnia 2017 w C i C++ przez mateuszX2k Nowicjusz (150 p.)
0 głosów
1 odpowiedź 271 wizyt
pytanie zadane 28 maja 2023 w C i C++ przez Szyszka Gaduła (3,490 p.)
0 głosów
2 odpowiedzi 204 wizyt
pytanie zadane 14 lutego 2018 w C i C++ przez Mipek Nowicjusz (150 p.)

92,453 zapytań

141,262 odpowiedzi

319,088 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!

...