小L的试卷

 

题目描述

小L期末考试结束，高高兴兴放假回家了，可是那么多试卷，老师还要加班批改，有n份试卷由k个老师批改，n份试卷进行了密封编号，由于试卷上的做题情况和书写的规范程序不一样，批改不同的试卷用时也可能不一样，每个老师批改试卷的编号顺序是连续的，每位老师批改完分配给自己的试卷就可以离开，问最后离开的老师，最短可能的用时是多少，假定一份试卷让任何一位老师批改用时都是一样的。现在请你设计一种分配方案，使得最后离开的老师用时最短。 

输入

第一行两个整数n，k；（0<k≤n≤1000） 

第二行n个整数，第i个整数表示批改第i份试卷的用时。 

输出

输出一个整数，表示最后离开的老师所用的最短时间

样例输入 Copy

9 3                              
1 2 3 4 5 6 7 8 9

样例输出 Copy

17

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;

int n , k;
ll a[maxn];

bool isok(int x)
{
    bool flag = false;
    int num = 0;
    ll temp = 0;
    for (int i=1; i<=n; i++)
    {
        if (a[i] > x)  return false;
        temp += a[i];
        if (temp > x)
        {
            num ++;
            temp = a[i];
        }
    }
    if (temp > 0)  num ++;
    if (num <= k)  return true;
    else  return false;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++)  scanf("%lld", &a[i]);
    ll l = 0 , r = inf;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (isok(mid))  r = mid-1;
        else  l = mid + 1;
    }

    cout << l << endl;
    return 0;
}