【九度1502】最大值最小化

淡淡的烟草味﹌ 2022-09-25 08:29 140阅读 0赞

题目1502：最大值最小化

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：566

解决：214

**题目描述：**

在印刷术发明之前，复制一本书是一个很困难的工作，工作量很大，而且需要大家的积极配合来抄写一本书，团队合作能力很重要。  
当时都是通过招募抄写员来进行书本的录入和复制工作的, 假设现在要抄写m本书，编号为1,2,3...m, 每本书有1<=x<=100000页，每页所用的时间是1分钟， 把这些书分配给k个抄写员，要求分配给某个抄写员的那些书的编号必须是连续的。每个抄写员的速度是相同的，你的任务就是找到一个最佳的分配方案，使得所有书被抄完所用的时间最少。

**输入：**

输入可能包含多个测试样例。  
第一行仅包含正整数 n，表示测试案例的个数。  
对于每个测试案例，每个案例由两行组成，在第一行中，有两个整数m和 k， 1<=k<=m<=500。 在第二行中，有m个整数用空格分隔。 所有这些值都为正且小于100000。

**输出：**

对应每个测试案例，  
输出一行数字，代表最佳的分配方案全部抄写完毕所需要的时间。

**样例输入：**

2
    9 3
    100 200 300 400 500 600 700 800 900
    5 4
    100 100 100 100 100

**样例输出：**

1700
    200

**来源：**

[网易有道2013年校园招聘面试一面试题][2013]

二分法求最大值最小化。

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

[题目地址：http://ac.jobdu.com/problem.php?pid=1502][http_ac.jobdu.com_problem.php_pid_1502]

[2013]: http://ac.jobdu.com/problemset.php?search=%E7%BD%91%E6%98%93%E6%9C%89%E9%81%932013%E5%B9%B4%E6%A0%A1%E5%9B%AD%E6%8B%9B%E8%81%98%E9%9D%A2%E8%AF%95%E4%B8%80%E9%9D%A2%E8%AF%95%E9%A2%98
[http_ac.jobdu.com_problem.php_pid_1502]: http://ac.jobdu.com/problem.php?pid=1502