题目:任务分配

题目描述

图书馆按顺序排列有N本书需要维护，每本书的总页数不相同。现有M位员工。可以给每个员工分配连续的一段书籍，让他进行维护。现在的问题是，怎么样分配，工作任务最重（需要维护的页数最多）的人维护的页数尽量少。

【数据规模和约定】
N<=10^5，M<=N。一本书的页数最多10^4。

输入格式

第一行两个数，N、M。接下来N行，每行一个整数，表示一本书的页数。

输出格式

任务最重的人最少需要维护的页数。

代码实现：

#include<iostream>
using namespace std;

int a[100001],m,n,mid;

int check(){
    int i=1,j=1,l=0;
    while(i<=n)
    {
     l+=a[i];
     if(l>mid) {j++;l=a[i];}   
     i++;         
               }
     if(j<=m) return 1;
     else return 0;  
    }

int main()
{
    int i,j,left=0,right=0;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
     cin>>a[i];
     right+=a[i];
     if(a[i]>left) left=a[i];
                     }
   
    while(left<right)
    {
     mid=(left+right)/2;
     if(check())
     right=mid;
     else left=mid+1; 
                     }

    cout<<right;
    return 0;
    }