Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
946 B
2
Indexable
Never
import java.util.Scanner;

public class Solution {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int t = 1; t <= T; t++) {
			int K = sc.nextInt();
			int N = sc.nextInt();
			int[] A = new int[N];

			int min = 0, max = 0, mid, sum, block;

			for (int i = 0; i < N; i++) {
				A[i] = sc.nextInt();
				if (A[i] > min) {
					min = A[i];
				}
				max += A[i];
			}

			while (max > min) {
				block = 0;
				mid = (max + min) / 2;
				sum = 0;

				for (int i = 0; i < N; i++) {
					if (sum + A[i] <= mid) {
						sum += A[i];
					} else {
						block++;
						sum = A[i];
					}
					if (i == N - 1) {
						block++;
					}
				}

				if (block <= K) {
					max = mid;
				} else {
					min = mid + 1;
				}
			}

			System.out.println("#" + t + " " + max);
		}
		sc.close();
	}

}