minimal big sum
unknown
plain_text
2 years ago
1.8 kB
5
Indexable
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); } } }
Editor is loading...