minimal big sum

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
1
Indexable
Never
package day18_2206;

import java.util.Scanner;

public class minimal_big_sum {
	
	static int k, n, ans, total, max;
	static int[] numbers, blocks;
	
//	private static int solve(){
//		int max = 0;
//		int start = 0, sum, j;
//		for(int i = 1; i < k; i++){
//			if(blocks[i] == n) return total;
//			if(blocks[i] != 0){
//				sum = 0; j = 0;
//				while(j < blocks[i]){
//					sum += numbers[start + j];
//					j++;
//				}
//				start += blocks[i];
//				max = max < sum ? sum : max;
//				if(max >= ans) return ans;
//			}
//		}
//		return max;
//	}
	
//	private static void sinh(int b, int cnt){
//		
//		if(b == k - 1){
//			blocks[b] = n - cnt;
//			int tmp = solve();
//			if(ans > tmp) ans = tmp;
//			return;
//		}
//		
//		for(int i = 0; i <= n; i++){
//			if(cnt + i <= n){
//				blocks[b] = i;
//				sinh(b + 1, cnt + i);
//			}
//			else break;
//		}
//	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
//			k = sc.nextInt() + 1;
			k = sc.nextInt();
			n = sc.nextInt();
//			blocks = new int[k];
			
			total = 0; max = 0;
			numbers = new int[n];
			for(int i = 0; i < n; i++){
				numbers[i] = sc.nextInt();
				total += numbers[i];
				max = max < numbers[i] ? numbers[i] : max;
			}
			ans = total;
//			sinh(1, 0);
			
			for(int i = max; i <= total; i++){
				int sum = 0, cnt = 1;
				for(int j = 0; j < n; j++){
					if(sum + numbers[j] > i){
						sum = numbers[j];
						cnt++;
					}
					else{
						sum += numbers[j];
					}
				}
				
				if(cnt <= k){
					ans = i;
					break;
				}
			}
			
			System.out.println("#" + tc + " " + ans);
		}
		
	}

}