Untitled

/*Minimal Big Sum
Suppose 'A' is a non empty zero indexed array of 'N' integers and 'K' is another Integer.
Array 'A' needs to be divided into 'K' blocks of consecutive elements.  


Size of the block is any integer such that , 0 <= size of block <= N. Every element of the array should belong to some block. 

The sum of the block from X to Y equals A[X] + A[X + 1] + ... + A[Y]. The sum of empty block equals 0.

The big sum is defined as the maximal sum of any block.

 

For example, you are given integers 'K' = 3 and array A such that:
  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2 

The array can be divided, for example, into the following blocks: 

        [2, 1, 5, 1, 2, 2, 2], [], [] with a big sum of 15;
        [2], [1, 5, 1, 2], [2, 2] with a big sum of 9;
        [2, 1, 5], [], [1, 2, 2, 2] with a big sum of 8;
        [2, 1], [5, 1], [2, 2, 2] with a big sum of 6.

 

The goal is to minimize the big sum. In the above example, 6 is the minimal big sum. 

 

Given integer K and a non-empty zero-indexed array A consisting of N integers, returns the minimal big sum. 

 

For example, given K = 3 and array A such that:
  A[0] = 2
  A[1] = 1
  A[2] = 5
  A[3] = 1
  A[4] = 2
  A[5] = 2
  A[6] = 2 

the function should return 6, as explained above.

 

Assume that: 

        N and K are integers within the range [1..100,000];
        each element of array A is an integer within the range [0..M]. 

Input :
First Line : T : Number of test cases
Second Line : K : Number of Blocks.
Third Line : N : Number of elements in the input array
Fourth Line : Elements of array separated by space.
Fifth Line : next test case follows 

 

Output
#Test_Case minimized_big_sum 

 

Sample Input
2
3
7
2 1 5 1 2 2 2
4
10
10 2 1 5 1 2 2 2 9 11 

 

Sample Output  

#1 6
#2 12


 * */

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MinimalBigSum2 {
	static{
		try {
			System.setIn(new FileInputStream("src/inp.txt"));
//			System.setOut(new PrintStream("src/out.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	static boolean div(int[] a,int k,long sum) {
		int n=a.length;
		long tmp=sum;
		
		for(int i=0;i<n;++i) {
			if(a[i]<=tmp) 
				tmp-=a[i];
			else if(sum>=a[i]) {
				tmp=sum-a[i];
				--k;
			}
			else			//NEU TIM THAY A[I] LON HON TONG CAN CHIA
				return false;
		}
		
		if(tmp>=0)		//xet TH CUOI CUNG
			--k;
		
		return k>=0;
	}
	
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		
		int t=Integer.parseInt(scanner.next());
		
		for(int test=1;test<=t;++test) {
			int k=Integer.parseInt(scanner.next());
			int n=Integer.parseInt(scanner.next());
			int[] a=new int[n];
			
			long s=0;
			for(int i=0;i<n;++i) {
				a[i]=Integer.parseInt(scanner.next());
				s+=a[i];
			}
			
			long l=0,r=s,
				res=s;	//NOTE: TRUONG HOP K=1 THI RES SE LA TONG LON NHAT LA TONG CUA CA DAY, DO NEU KO DAT RES=1 THI KO THE DUYET DEN M=TONG CUA CA DAY DO R-L>1
			while(r-l>1) {
				long m=l+(r-l)/2l;
				
				if(div(a, k, m)) {//NEU CO THE CHIA THANH K DAY CON CO TONG<=M, THI GIAM TONG M DE TIM TONG MIN
					r=m;
					res=m;
				} else	//NEU KO CHIA DC THI TANG TONG LEN
					l=m;
			}
			
			System.out.printf("#%d %d\n",test,res);
		}
		
		scanner.close();
	}
}