巢穴

about:blank

P3273

 

#include <iostream>
using namespace std;

int n,m;
int const MAXN=100010;
int num[MAXN];
int main()
{
    cin>>n>>m;
    int l=0,r=0;
    for (int i=1;i<=n;i++)
    {
        cin>>num[i];
        r+=num[i];
        if (l<num[i]) l=num[i];
    }
    int mid;
    while(l<=r)
    {
     mid=(l+r)/2;

     int count=1,sum=0;
     int max_=-1;
     for (int i=1;i<=n;i++)
     {
      if (num[i]>mid) {count=m+1;break;}
      if (sum+num[i]<=mid) sum+=num[i]; 
      else 
      {
       sum=num[i];count++;
      }
      if (max_<sum) max_=sum;
     }
      if (count<=m) {r=mid-1;}
     else l=mid+1;
    }
    cout<<l<<endl;

    return 0;
}

练2分- -

posted on 2009-11-09 22:00 Vincent 阅读(131) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理