【暑期训练3】晴天系列D题

缺乏、安全感 2022-09-25 08:29 119阅读 0赞

## Problem F: D ##

Time Limit: 1 Sec Memory Limit:  128 MB  
Submit: 178 Solved: 38  
  
[Submit][] [Status][] [Web Board][]

## Description ##

晴天想把一个包含n个整数的序列a分成连续的若干段，且和最大的一段的值最小，但他有强迫症，分的段数不能超过m段，然后他就不会分了。。。他想问你这个分出来的和最大的一段的和最小值是多少？

## Input ##

第一行输入一个整数t，代表有t组测试数据。  
每组数据第一行为两个整数n,m分别代表序列的长度和最多可分的段数。  
接下来一行包含n个整数表示序列。  
0<=n<=50000 1<=m<=n，0<=ai<=10000。

## Output ##

输出一个整数表示和最大的一段的最小值。

## Sample Input ##

1
    3 2
    1 3 5

## Sample Output ##

## HINT ##

1 3 5 分成一段可以为1 3 5和为9，分成两段可以为1，3 5或者1 3，5，和最大的一段值分别为8，5，所以答案为5

二分法求最大值最小化：

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 50000+10;
    int a[N];
    int n,m;
    bool judge(int mid) {
    	int sum=0,count=1;
    	for(int i=0; i<n; i++) {
    		//	printf("---\n");
    		if(sum+a[i]<=mid) {
    			sum+=a[i];
    		} else {
    			count++;
    			sum=a[i];
    		}
    	}
    	return count<=m;
    }
    int main() {
    	int T;
    	scanf("%d",&T);
    	while(T--) {
    		scanf("%d%d",&n,&m);
    		int l=0,r=0;
    		for(int i=0; i<n; i++) {
    			scanf("%d",&a[i]);
    			r+=a[i];
    			l=max(l,a[i]);
    		}
    		int mid,ans;
    		while(l<=r) {
    			mid=(l+r)/2;
    			if(judge(mid)) {
    				ans=mid;
    				r=mid-1;
    			} else {
    				l=mid+1;
    			}
    		}
    		//	printf("---\n");
    		printf("%d\n",ans);
    	}
    	return 0;
    }

[题目地址：http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1919][http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1919]

[Submit]: http://acm.zzuli.edu.cn/zzuliacm/submitpage.php?cid=1159&pid=5&langmask=0
[Status]: http://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=1919
[Web Board]: http://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=1919&cid=1159
[http_acm.zzuli.edu.cn_zzuliacm_problem.php_id_1919]: http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1919