@dmitrii2004

Найти количество чисел меньше заданного?

На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших заданного в запросе числа. Использовать встроенные функции бинарного поиска запрещено.

Входные данные

Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.
Вторая строка содержит N целых чисел Ai через пробел. −109≤Ai≤109.
Третья строка содержит число M — количество запросов. 1≤M≤250000.
Четвёртая строка содержит M целых чисел Qi через пробел. −109≤Qi≤109.

Выходные данные

Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших соответствующего запроса.

Примеры
Ввод
Вывод
5
1 5 3 2 1
2
4 3
Вывод
4 3
Ограничения
Время выполнения: 3 секунды
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
	unsigned int n;
	cin >> n;
	int* A = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> A[i];
	}
	sort(A, A + n);
	int m;
	cin >> m;
	int x = m;
	int* B = new int[m];
	for (int i = 0; i < m; i++)
	{
		cin >> B[i];
	}
	int f = 250000;
	int* V = new int[f];
	for (int i = 0; i <m; i++)
	{
		int L = -1;
		int R = n;
		while (R - L > 1)
		{
			m = (R + L) / 2;
			if (A[m] < B[i])
			{
				L = m;
			}
			else
			{
				R = m;
			}
		}
		V[i] = R;
	}
	for (int i = 0; i < x; i++)
	{
		cout << V[i] << " ";
	}
}

Помогите пожалуйста ! Сайт пишет, что программа выдаёт неверный ответ
  • Вопрос задан
  • 218 просмотров
Решения вопроса 2
Alexandroppolus
@Alexandroppolus
кодир
массив А надобно отсортировать для бинарного поиска.

if(A[m<i]) нет ли тут какой ошибки?
Ответ написан
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Куча ошибок. Вы читаете запросы в массив B и больше нигде не используете. Конструкция A{m<i] вообще удивительна. Массив надо отсортировать.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы