8. 装果子
XJOI - 题目ID：2056必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Time Limit Exceeded
70 分
时间限制: 1000ms
空间限制: 131072kB
题目描述
时间限制: 1s 空间限制: 128M
题目描述:
果园里有n颗果树，每棵果树都有一个编号i(1≤i≤n)。小明已经把每棵果树上的果子都摘下来堆在了这棵树的下方，每棵树下方的果子体积为ai。
现在小明将拿来m个袋子把这些果子都装进袋子里。每个袋子的体积为v。小明会按照如下规则把果子装进袋子里：
(a)从第1棵果树开始装起，由1到n一直装到第n棵果树。
(b)如果这棵果树下的果子能全部装进当前这个袋子，就装进去；如果不能，就关上当前这个袋子，打开一个新的袋子开始装。
小明希望在能把所有果子都装进袋子里的前提下，v尽量小。m个袋子并不一定都要装进果子。
输入格式：
输入第1行，包含两个整数n和m。
第2行，包含n个整数ai。
输出格式：
输出仅1行，表示最小的v。
样例输入1:
3 3 1 2 3
样例输出1:
3
样例输入2:
5 3 1 3 6 1 7
样例输出2:
7
样例输入3:
6 3 1 2 1 3 1 4
样例输出3:
4
数据范围：
对于40%的数据 1≤ai≤1000
对于70%的数据 1000≤ai≤100000
对于100%的数据小于 1≤n≤100000，1≤m≤1000，100000≤ai≤1000000000
提示：
【输入输出样例解释1】
每个袋子的体积为3即可。前2棵果树的果子装在第一个袋子里，第3棵果树的果子装在第二个袋子里。第三个袋子不用装了。
【输入输出样例解释2】
每个袋子的体积为7即可。前2棵果树的果子装在第一个袋子里，此时第一个袋子已经装了4单位体积的果子，第3棵果树的果子装不下了，所以装进第二个袋子里，第4棵果树的果子刚好装进第二个袋子，第5棵果树的果子装进第三个袋子里。
【输入输出样例解释3】
每个袋子的体积为4即可。前3棵果树的果子装在第一个袋子里，第4~5棵果树的果子装在第二个袋子里，第6棵果树的果子装在第三个袋子里。
代码：
#include<iostream>
using namespace std;
int n,m;
long long a[100005];
long long s=0;
bool check(long long x){
long long sum=1,t=0;
for(int i=1;i<=n;i++){
t+=a[i];
if(t>x){
t=a[i];
sum++;
}
if(sum>m){
return false;
}
}
return sum<=m;
}
int main(){
cin>>n>>m;
long long maxx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
s+=a[i];
maxx=max(maxx,a[i]);
}
long long l=maxx,r=s;
while(l<r){
int mid=(l+r)/2;
if(check(mid)){
r=mid;
}
else{
l=mid+1;
}
}
cout<<r;
return 0;
}