Interesting Drink
A drink is sold in \(n\) shops. A bottle costs \(x_i\) coins in the \(i\)-th shop. For \(q\) days you know that on the \(i\)-th day Vasiliy can spend \(m_i\) coins. For each day, find the number of shops in which Vasiliy can buy a bottle.
Constraints:
- \(1 \le n \le 10^5\), \(1 \le x_i \le 10^5\)
- \(1 \le q \le 10^5\), \(1 \le m_i \le 10^9\)
Input:
- First line: integer \(n\) — the number of shops.
- Second line: \(n\) integers \(x_1, x_2, \dots, x_n\) — the prices.
- Third line: integer \(q\) — the number of days.
- Next \(q\) lines: one integer \(m_i\) per line.
Output:
- \(q\) lines — for each day, the number of shops with price at most \(m_i\).
Example:
Input:
5
3 10 8 6 11
4
1
10
3
11
Output:
0
4
1
5
Solution
Checking all shops for every day takes \(O(n \cdot q)\) time, which is up to \(10^{10}\) operations and too slow.
Instead, we sort the prices once. In the sorted array, the prices at most \(m\) form a prefix. If first is the position of the first price greater than \(m\), then the prefix has exactly first elements, so first is the answer. If there is no such price, the answer is \(n\).
We find first with the binary search from the lesson for the first element greater than or equal to \(X\); the only change is the condition x[mid] > m.
Sorting takes \(O(n \log n)\) time and each day takes \(O(\log n)\) time, so the whole solution takes \(O((n + q) \log n)\) time.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> x(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
}
sort(x.begin(), x.end());
int q;
cin >> q;
for (int day = 0; day < q; day++) {
int m;
cin >> m;
// find the first position with a price greater than m
int left = 0, right = n - 1;
int first = n;
while (left <= right) {
int mid = (left + right) / 2;
if (x[mid] > m) {
first = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << first << "\n";
}
}