题目
| 小升初2：废品回收 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
江北榨油厂每天会产生一批废料，厂方会按照日期批次封装起来等待回收。现在积攒了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
|
分析
这题算得上前100题里最难的了。要么搜索，要么二分。如果您是新手的话，可以先跳过。但理解一下，烧脑一下，还是挺好的~
主要还是二分的思路。没学的就先别看了。
通过读入时累加最大值和“打擂台”比较最小值确定左右端点，在通过累加当前情况所需钱数判断是否满足条件，并同时根据情况改变端点。最终当左右端点相等时即所有情况判断完成时，输出左右端点中的任意一个即可。
搜索的代码在这里就不给了，基本和二分的代码一样，搜到了再次调用就行了。
代码
#include<bits/stdc++.h>
using namespace std;
int a[100005],m,n,sum,mid,l,r,s;
int main()
{
scanf("%d%d",&n,&m);//本代码使用分治算法解决，若不能理解分治算法的基本思想，请勿抄袭！为自己带来不必要的损失！
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
r+=a[i];//计算最右端点。
if(a[i]>l) l=a[i];//计算最左端点。
}
while(l<r)//二分条件成立。
{
mid=(l+r)/2;//计算当前中点。
sum=1;
s=0;
for(int i=0;i<n;i++)//统计总钱数。
{
s+=a[i];
if(s>mid)
{
sum++;
s=a[i];
}
if(sum>m) break;//如果赊账了，说明该方案不行，结束统计，更改端点。
}
if(sum>m) l=mid+1;//右移左端点。
else r=mid;//左移右端点。
}
printf("%d",l);//输出l和r中的一个端点就行。
return 0;
}
搜索的代码：
#include<bits/stdc++.h>//搜索涉及到对函数的调用，看不懂更别抄！！！
using namespace std;
int a[100005],n,m,maxn=-1,sum,mid,cnt;//maxn给一个很小的值方便读入和特判。
void dfs(int l,int r)
{
if(l>=r)//和二分没有本质区别
{
printf("%d",l);
return;
}
mid=(l+r)/2;
cnt=1;
sum=0;
for(int i=0;i<n;i++)
{
sum+=a[i];
if(sum>mid)
{
sum=a[i];
cnt++;
}
if(cnt>m) break;
}
if(cnt>m) dfs(mid+1,r);
else dfs(l,mid);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
if(a[i]>maxn) maxn=a[i];
}
dfs(maxn,sum);
return 0;
}