Zadanie z wyszukiwaniem binarnym po wyniku.

Question

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;
}

 

Answer 1

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 )