[Codeforces Round #790 (Div. 4)] E. Eating Queries

 

 

---

※ 섭취해야 하는 설탕의 양이(x)  모든 사탕의 합보다 크다면 -1을 출력

※ 설탕의 양이 사탕의 합과 같다면 사탕의 갯수(n) n을 출력

※ 사탕의 정보가 있는 배열을 정렬한 후 가장 설탕이 많은 사탕부터 사탕 갯수당 설탕의 양을 나타내는 배열을 만든다

 (1,1,3,3,4,4,5,9) -> (9, 9+5, 9+5+4, 9+5+4+4, ... 9+5+4+4+3+3+1+1)

※ n, q가 150,000 이므로 nq가 아닌 q*log n 인 이분탐색으로 찾아야함

 

1.사탕 갯수마다 설탕의 합을 나타내는 dp배열을 생성

2. x가 sum(설탕의 합)보다 크면 -1 같으면 n

3. 나머지 경우는 이분탐색으로 dp배열을 탐색

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		while(T --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int Q = Integer.parseInt(st.nextToken());
			st = new StringTokenizer(br.readLine(), " ");
			long[] arr = new long[N];
			long sum = 0;
			for(int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
				sum += arr[i];
			}
			Arrays.sort(arr);
			long[] dp = new long[N+1];
			
			int cnt = 1;
			for(int j = N-1; j >= 0; j--) {
				dp[cnt] = dp[cnt-1] + arr[j];
				cnt++;
			}
			//System.out.println(Arrays.toString(dp));
			for(int i = 0; i < Q; i++) {
				st = new StringTokenizer(br.readLine());
				long a = Integer.parseInt(st.nextToken());
				if(sum < a) {
					sb.append(-1).append('\n');
				}
				else if(sum == a) {
					sb.append(N).append('\n');
				}
				else {
					int temp = 0;
					int lo = 1;
					int hi = N+1;
					while(lo < hi) {
						int mid = (lo+hi) / 2;
						if(dp[mid] < a) {
							lo = mid+1;
						}
						else {
							hi = mid;
						}
					}
					sb.append(lo).append('\n');
				}
			}
		}
		System.out.println(sb);
    }
}