51nod 1128 正整数分组 V2 二分答案

1128 正整数分组 V2

基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

收藏

关注

给出一个长度为N的正整数数组，不改变数组元素的顺序，将这N个数分为K组。各组中元素的和分别为S1,S2....Sk。如何分组，使得S1至Sk中的最大值最小？

例如：1 2 3 4 5 6分为3组，{1 2 3} {4 5} {6}，元素和为6, 9, 6，最大值为9。也可以分为{1 2 3 4} {5} {6}。元素和为：10 5 6，最大值为10。因此第一种方案更优。并且第一种方案的最大值是所有方案中最小的。输出这个最小的最大值。

Input

第1行：2个数N, K，中间用空格分隔，N为数组的长度，K为要分为多少组。(2 <= K < N <= 50000)第2 - N + 1行：数组元素(1 <= A[i] <= 10^9)

Output

输出这个最小的最大值。

Input示例

6 3123456

Output示例

9

思路：二分答案，连续的和大于mid前面的数就是一组，最后得出最小的最大值。

Code：

#include <bits/stdc++.h>
#define LL long long 
using namespace std;
const int AX = 5e4+66;
int a[AX];
int n , m;
int fun( LL x ){
	LL s = 0LL;
	int tot = 0 ;
	for( int i = 0; i < n ; i ++ ){
		s += a[i];
		if( s >= x ){
			if( s > x ){
				i--;
			}
			s = 0 ;
			tot ++;
		}
	}
	if( s ) tot ++ ;
	return ( (tot <= m ) ? 1 : 0 );
}

int main(){
	ios_base::sync_with_stdio(false) ;
	cin >> n >> m;
	LL sum = 0LL;
	int maxn = -1;
	for( int i = 0 ; i < n ; i++ ){
		cin >> a[i];
		maxn = max( maxn , a[i] );
		sum += a[i];
	}
	LL l = maxn;
	LL r = sum;
	while( l <= r ){
		LL mid = ( l + r ) >> 1;
		if( fun(mid) ){
			r = mid - 1 ;
		}else{
			l = mid + 1 ;
		}
	}
	cout << l << endl;
	return 0 ;
}