|
试题描述
|
|
江北榨油厂每天会产生一批废料，厂方会按照日期批次封装起来等待回收。现在积攒了n天的废料，厂里财务记录下了每天产生废料合同价值。现在回收站委托星空运输公司将这n天的废料分m次回收，要求按照日期的先后顺序回收，回收站每次拨给运输公司的经费是一个定值ans，油厂老板每次允许运走的废料是不允许赊账的，所以运输公司每次运走的废料价值一定不会超过ans，若运输公司想运走第i天的废料，必须运走第i天及之前所有还没有运走的废料。对回收站来说，他的拨款不但要保证运输公司能够恰好m次运回所有的废料，而且拨款越少越好。请你编写程序求出符合回收站要求的每次拨款数额。
|
|
输入
|
|
第一行输入两个用空格隔开的正整数n和m 接下来有n个由空格隔开不超过10000正整数，依次表示每一天产生废料的价值。
|
|
输出
|
|
输出包含一个整数，即回收站每次拨款的数额
|
|
输入示例
|
|
7 5 100 400 300 100 500 101 400
|
|
输出示例
|
|
500
|
|
其他说明
|
|
数据范围：1<=m<=n<=100000
|
#include
#include
#include
using namespace std;
int a[100005],m,n;
bool flag(int x)
{
int sum=0,step=1;
for(int i=1;i<=n;i++)
{
if(a[i]>x)
return 0;
if(sum+a[i]<=x)
sum+=a[i];
else
{
sum=a[i];
step++;
if(step>m)
return 0;
}
}
return 1;
}
int main()
{
int tail=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
tail+=a[i];
}
int head=0,mid;
while(head+1<tail)
{
mid=(head+tail)/2;
if(flag(mid)==1)
tail=mid;
else
head=mid;
}
printf("%d",tail);
//system("pause");
}