Question

Buna!
Ma poate ajuta cineva cu problema asta? Nu o pot rezolva nicicum.

#2443 cb2
Clasa a 9-a Tablouri unidimensionale (vectori) Căutare binară cb2
Etichete: Cautare binară



Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări. Fiecare interogare este dată de o pereche (x, s): care este indicele maxim p cu proprietatea că a[i] ≤ x, pentru orice i=1..p și în plus a[1] + a[2] + ... + a[p] <= s?

Cerința
Trebuie să răspundeți la fiecare din cele Q întrebări.

Date de intrare
Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații, reprezentând elementele șirului. Apoi se citește valoarea Q și la final se citesc Q perechi de forma (x, s) reprezentând întrebările.

Date de ieșire
Programul va afișa pe câte o linie la ecran Q valori reprezentând răspunsurile la întrebări.

Restricții și precizări
1 ≤ n ≤ 100 000
1 ≤ Q ≤ 100 000
1 ≤ a[i] ≤ 1 000 pentru orice i=1..n
pentru fiecare întrebare, 1 ≤ x, s ≤ 1 000 000 000

Exemplu
Intrare

9
5 3 1 7 4 9 8 2 6
6
8 10
4 20
6 20
6 8
10 100
10 20
Ieșire

3
0
3
2
9
5
Explicație
La prima întrebare, x=8, s=10. Indicele maxim este 3 pentru că primele trei valori din șir sunt mai mici sau egale cu 8, iar 5 + 3 + 1 ≤ 10.
La a doua întrebare, răspunsul este 0 deoarece primul număr din șir este 5 care este mai mare decât x=4.
La a cincea întrebare, x=10 și s=100. Răspunsul este chiar lungimea șirului.


Eu am reusit sa fac codul asta, dar nu e bun deloc:
#include

using namespace std;
int a[100001],n,i,q,x,s;
int p=0;
int caut1(int x,int s)
{
for (i=1; i<=n;i++)
if (a[i]<=x)
p++;
return p;
}
int caut2(int s)
{
int sum=0;
if (sum for (i=1; i<=p;i++)
{
if (sum sum=sum+a[i];
q++;
}
return q;
}
bool compar (int q, int p)
{
if (p==q);
return true;
}
int main()
{
int c1,c2;
cin >>n;
for (i=1; i<=n;i++)
cin >>a[i];
cin >>q;
for (i=1; i<=q;i++)
{
cin >>x>>s;
c1=caut1(x,s);
c2=caut2(s);
if (compar(c1,c2))
cout <

}
return 0;
}

Answer 1

Răspuns:

#include <iostream>

using namespace std;

int main()

{

   int n,a[50],sum[50]={0},q,ct[50]={0},i,x,s;

   cin>>n;

   for(i=1;i<=n;i++)

   {

       cin>>a[i];

       sum[i]=sum[i-1]+a[i];

   }

   cin>>q;

   for(i=1;i<=q;i++)

   {

       cin>>x>>s;

       ct[i]=1;

       while(a[ct[i]]<=x && sum[ct[i]]<=s)

       {

           ct[i]++;

       }

   }

   for(i=1;i<=q;i++)

   {

       cout<<ct[i]-1<<endl;

   }

   return 0;

}

Explicație:

Salut, m-am gandit sa-ti scriu o metoda iterativa si am folosit m-am bazat pe vectori in special. Daca nu intelegi ceva te rog scrie-mi si te voi ajuta. Sper ca iti va fi de folos.