废品回收

试题描述 江北榨油厂每天会产生一批废料，厂方会按照日期批次封装起来等待回收。现在积攒了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 <iostream> #include <cstdio> #include <cmath> 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"); } View Code

 

转载于:https://www.cnblogs.com/jason2003/p/6572229.html

相关资源：宏达废品回收公司管理系统破解版