← 返回 microsoft 的题目列表Maximum Purchases From Sorted Prices Starting at Position (Multiple Queries)
类型：online_judge
Problem
You are given an integer array prices of length n sorted in non-decreasing order, and q queries. Each query provides:
pos: a starting position
amount: the amount of money you have
For each query, compute the maximum number of products you can buy without exceeding amount.
Rules:
Each price corresponds to one product; you can buy each product at most once.
You may only buy products with indices i >= pos.
You may choose any subset from the allowed range (not necessarily contiguous) to maximize the number of products.
Return an array ans of length q where ans[j] is the result for the j-th query.
Input
Line 1: integer n
Line 2: n integers prices[0..n-1] (non-decreasing)
Line 3: integer q
Next q lines: two integers pos amount
Output
One line with q integers separated by spaces.
Constraints (suggested)
1 <= n, q <= 2 * 10^5
0 <= pos < n
0 <= prices[i], amount <= 10^9
Example
Input:
5
2 2 3 5 8
3
0 7
2 10
4 7
Output:
3 2 0
Example
Input
5
2 2 3 5 8
3
0 7
2 10
4 7
Output
3 2 0