# minimal big sum

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] != 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);
}

}

}
```