# Untitled

unknown
plain_text
a year ago
3.6 kB
5
Indexable
Never
```/*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();
}
}
```