Masz daną posortowaną tablicę liczb nieujemnych nie dłuższą niż milion elementów. Dla każdego zapytania o liczbę x odpowiedz, ile liczb w tej tablicy jest niemniejszych niż xi.
Wejście: W pierwszej linii dana jest liczba n (1 ≤ n ≤ 1000000), oznaczająca długość tablicy. Następnie dane jest n nieujemnych liczb w kolejności niemalejącej, które stanowią zawartość tablicy. W drugiej linii dana jest liczba m (1 ≤ m ≤ 1000000), oznaczająca ilość zapytań. Następnie danych jest m liczb xi.
Wyjście: Dla każdego z m zapytań wypisz odpowiedź - ilość liczb niemniejszych od liczby x z zapytania.
Przykład:
Dla danych wejściowych
10 3 4 8 11 23 54 996 8710 911147 10001010
10 1 0 8 64 99 114 334 8484 41 911147
poprawną odpowiedzią jest
10 10 8 4 4 4 4 3 5 2
Oto napisany przeze mnie kod:
Kod: Zaznacz cały
#include<iostream>
using namespace std;
int main()
{
int n, i;
cin >> n;
int a[n];
for (i=0; i<n; i++)
{
cin >> a[i];
}
int m, j;
cin >> m;
int b[m];
for (j=0; j<m; j++)
{
cin >> b[j];
}
for (j=0; j<m; j++)
{
if (b[j]<=a[0]) cout << n << " ";
else
{
int k=0;
for (i=n-1; i>=0; i--)
{
if (a[i]<b[j]) break;
else k++;
}
cout << k << " ";
}
}
return 0;
}