Eating Queries (Codeforces 1676E)
Tags: Greedy, binary search

Timur has $$$n$$$ candies. The $$$i$$$-th candy has a quantity of sugar equal to $$$a_i$$$. So, by eating the $$$i$$$-th candy, Timur consumes a quantity of sugar equal to $$$a_i$$$.Timur will ask you $$$q$$$ queries regarding his candies. For the $$$j$$$-th query you have to answer what is the minimum number of candies he needs to eat in order to reach a quantity of sugar greater than or equal to $$$x_j$$$ or print -1 if it's not possible to obtain such a quantity. In other words, you should print the minimum possible $$$k$$$ such that after eating $$$k$$$ candies, Timur consumes a quantity of sugar of at least $$$x_j$$$ or say that no possible $$$k$$$ exists.Note that he can't eat the same candy twice and queries are independent of each other (Timur can use the same candy in different queries).

Input: The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$)  — the number of test cases. The description of test cases follows.The first line contains $$$2$$$ integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 1.5\cdot10^5$$$) — the number of candies Timur has and the number of queries you have to print an answer for respectively.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^4$$$) — the quantity of sugar in each of the candies respectively.Then $$$q$$$ lines follow. Each of the next $$$q$$$ lines contains a single integer $$$x_j$$$ ($$$1 \leq x_j \leq 2 \cdot 10^9$$$) – the quantity Timur wants to reach for the given query.It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$1.5 \cdot 10^5$$$.

Output: For each test case output $$$q$$$ lines. For the $$$j$$$-th line output the number of candies Timur needs to eat in order to reach a quantity of sugar greater than or equal to $$$x_j$$$ or print -1 if it's not possible to obtain such a quantity.

Note: For the first test case:For the first query, Timur can eat any candy, and he will reach the desired quantity.For the second query, Timur can reach a quantity of at least $$$10$$$ by eating the $$$7$$$-th and the $$$8$$$-th candies, thus consuming a quantity of sugar equal to $$$14$$$.For the third query, there is no possible answer.For the fourth query, Timur can reach a quantity of at least $$$14$$$ by eating the $$$7$$$-th and the $$$8$$$-th candies, thus consuming a quantity of sugar equal to $$$14$$$.For the second test case:For the only query of the second test case, we can choose the third candy from which Timur receives exactly $$$3$$$ sugar. It's also possible to obtain the same answer by choosing the fourth candy.

Sample Inputs:
3
8 7
4 3 3 1 1 4 5 9
1
10
50
14
15
22
30
4 1
1 2 3 4
3
1 2
5
4
6

Sample Outputs:
1
2
-1
2
3
4
8
1
1
-1

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def read_str():
    return input().strip()

def read_int():
    return int(input())

def read_map():
    return map(int, input().split())

def read_lst():
    return list(map(int, input().split()))
''
import bisect

def solve():
    (n, q) = read_map()
    arr = read_lst()
    arr.sort(reverse=True)
    pref = [0] * n
    pref[0] = arr[0]
    for i in range(1, n):
        pref[i] = pref[i - 1] + arr[i]
    for _ in range(q):
        x = read_int()
        if x > pref[-1]:
            print(-1)
            continue
        print(bisect.bisect_left(pref, x) + 1)
for _ in range(read_int()):
    solve()

Solution (Python):
import sys
import bisect
for _ in range(int(input())):
    (N, Q) = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    B = [0] * N
    B[-1] = A[-1]
    for i in range(N - 2, -1, -1):
        B[i] = B[i + 1] + A[i]
    B.reverse()
    for _ in range(Q):
        x = int(sys.stdin.readline())
        i = bisect.bisect_left(B, x)
        ans = i + 1
        print(ans if ans <= N else -1)

Solution (Python):
import bisect, sys
from itertools import accumulate
input = sys.stdin.readline
for g in range(int(input())):
    (n, q) = list(map(int, input().split()))
    s = sorted(list(map(int, input().split())), reverse=True)
    p = [0] * len(s)
    p = list(accumulate(s))
    for _ in range(q):
        test = int(input())
        if p[-1] < test:
            print(-1)
        else:
            k = bisect.bisect_left(p, test)
            print(k + 1)