Для каждого из дней узнать в каком количестве магазинов можно купить одну бутылочку напитка

@smdjn · Регистрация: 03.04.2020

Студворк — интернет-сервис помощи студентам

ограничение по времени на тест 2 секунды
Рабочий Василий очень любит отдыхать после работы, поэтому его часто можно встретить в каком-нибудь баре. Как и все программисты, Василий очень любит напиток «Пикола», который продаётся в n различных магазинах города. Известно, что в i-м магазине бутылка напитка стоит xi монет.

Василий планирует покупать одну бутылку своего любимого напитка на протяжении q дней. Он знает, что в i-й день у него с собой будет mi монет, и теперь он хочет для каждого из дней узнать, в каком количестве магазинов он сможет купить одну бутылочку Пиколы.

Входные данные
В первой строке входных данных содержится целое число n (1 ≤ n ≤ 100 000) —количество магазинов в городе, продающих любимый напиток Василия.

Во второй строке входных данных содержится n чисел xi (1 ≤ xi ≤ 100 000) — цена за одну бутылку напитка в i-м магазине.

В третьей строке входных данных содержится число q (1 ≤ q ≤ 100 000) —количество дней, в течение которых Василий планирует покупать напиток.

В следующих q строках входных данных содержатся целые числа mi (1 ≤ mi ≤ 109) — количество денег, которое есть у Василия в i-й день.

Выходные данные
Выведите q целых чисел, i-е из которых должно равняться количеству магазинов, в которых Василий может купить одну бутылочку любимого напитка в день i.

Пример
входные данные
5
3 10 8 6 11
4
1
10
3
11
выходные данные
0
4
1
5
Примечание
В первом запросе ни в одном магазине Василию не хватит денег.

Во втором запросе Василию хватит денег, чтобы купить напиток в магазинах под номерами 1, 2, 3 и 4.

В третьем запросе Василию хватит денег, чтобы купить напиток в магазине под номером 1.

И в последнем запросе Василий может купить свой напиток в любом магазине.

пробовал решить так, но не прошло по времени

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n, a, c, d;
    cin >> n;
    vector <int> mag;
    vector <int> day;
    for (int i = 0; i < n; i++){
        cin >> a;
        mag.push_back(a);
    }
    cin >> c;
    for (int i = 0; i < c; i++) {
        cin >> d;
        day.push_back(d);
    }
    for (int i = 0; i < c; i++) {
        int schet = 0;
        for (int j = 0; j < n; j++) {
            if (mag[j] <= day[i]) schet++;
        }
        cout << schet << endl;
    }
    return 0;
}

@Fixer_84 · 10.04.2020, 12:01

smdjn, здравствуйте! Вот решение:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>
 
    using namespace std;
 
int main() {
    int n, q, m, k;
    cin >> n;
    vector < int > v(n+1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    cin >> q;
    for (int j = 1; j <= q; j++) {
        cin >> m;
        k = upper_bound(v.begin(), v.end(), m) - v.begin();
        cout << --k << "\n";
    }
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .