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. Sam zamysł wyszukiwania binarnego po wyniku myślę, że rozumiem i potknąłem się w implementacji, ale nie potrafię sam zobaczyć, co zrobiłem źle.
Mamy daną tablicę n liczb całkowitych. Dla każdego elementu tej tablicy szukamy minimalnego promienia r, takiego że suma wszystkich elementów oddalonych o maksymalnie r od tego elementu jest równa lub większa od pewnej ustalonej wartości w.
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,...t(n-1)(1<= t <= 1 000 000), gdzie t(i) ozn. wartość i-tego elementu tablicy, a w trzecim wierszu n licz całk w0, w1, w2,... w(n-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...r(n-1), gdzie r(i) 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;
}