Question

Buna!
Ma poate ajuta cineva la problema #2789 cb3 de pe pbinfo??

Se consideră un șir de numere naturale nenule a[1], a[2], …, a[n]. Asupra șirului se efectuează Q interogări de forma: care este numărul maxim de elemente ale șirului a căror sumă nu depășește valoarea S ?

Cerință
Trebuie să răspundeți la cele Q interogări.

Date de intrare
Fișierul de intrare cb3.in conține pe prima linie numerele n și Q. Pe a doua linie n numere naturale nenule, separate prin spații, ce reprezintă elementele șirului. Pe următoarele Q linii se află sumele aferente celor Q interogări.

Date de ieșire
Fișierul de ieșire cb3.out va conține pe câte o linie răspunsurile la cele Q interogări.

Restricții și precizări
1 ≤ n ≤ 10000
1 ≤ Q ≤ 100000
1 ≤ S ≤ 2.000.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu
cb3.in

5 3
1 2 3 4 5
6
17
5
cb3.out

3
5
2
Multumesc!

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

#include <algorithm>

using namespace std;

ifstream f("cb3.in");

ofstream g("cb3.out");

int v[10002], n, q, i, sp[10002],s;

int bsearch1 (int p, int u, int key) {

   int m;

   while (p < u){

       m = (p + u) / 2;

       if (sp[m] <= key)

           p = m + 1;

       else

           u = m;

   }

   m = (p + u) / 2;

   if (sp[m] > key)

      -- m;

   return m;

}

int main()

{

   f >> n >> q;

   for (i=1; i<=n; ++i) f >> v[i];

   sort(v+1,v+n+1);

   sp[1]=v[1];

   for (i=2; i<=n; ++i) sp[i]=sp[i-1]+v[i];

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

   {

       f >> s;

       g << bsearch1(1,n,s) << "\n";

   }

}

Explicație:

sortăm crescător vectorul iniţial, cream alt vector cu sume partiale şi căutare binară în el