- #include<iostream>
- using namespace std;
- #define MAX 100000+200
- long long wei[MAX];
- long long n,m;
- /* 袋子的最小值是最大一堆果子的体积, 最大值是所有果子的体积
- 函数 参数是此时袋子的体积 v
- */
- long long split(long long v)
- {
- long long num = 1,hold =0;//num 存放已使用多少个袋子, hold 表示当前袋子已经装了多少
- for(long i=0;i<n;i++)
- {
- hold += wei[i];
- if(hold>v)
- {
- num++;
- hold = wei[i];
- }
- }
- return num; // 返回所使用袋子的个数
- }
- void solve(long long l,long long h)
- {
- long long lw = l,hw = h,mw ;
- for(int i=0;i<300;i++)
- {
- mw = (lw+hw)/2;
- if(split(mw)>m)
- {
- lw = mw;
- }else{
- hw = mw;
- }
- }
- cout<<hw<<endl;
- }
- int main()
- {
- long long sumw = 0,maxw = 0;
- cin>>n>>m;//m 袋子的总个数, n 是果树的总个数
- for(long i=0;i<n;i++)
- {
- cin>>wei[i];
- sumw+=wei[i];
- maxw = max(maxw,wei[i]);
- }
- solve(maxw,sumw);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2506115.html