ACM模版

描述

题解

这道题，话题是二分，并且讨论区中 qwb 说这是五级题中最最最简单的题了，于是我也只好向着二分想，可是我想了十几分钟也没有想通如何二分，大概是我思维闭塞吧，二分没有用到精髓，看了讨论区的大致思路，一下子就明白了，二分+贪心。

首先求所有数的和，然后二分之，根据每一个 mid 判断是否有合法的分割手法，当然这个判断用的就是贪心的思维，代码十分容易理解，作为职业马后炮，我必须说，这个题是五级题最简单的了，如果你大脑没有抽筋儿的话。像我这种大脑别跟儿筋的人，越是往二分想，越卡壳，因为只想着二分搞，却忽略了需要结合贪心判定。

代码

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 5e4 + 10;

int N, K;

ll A[MAXN];

int check(ll num)
{
    int m = K;
    ll sum = 0;
    for (int i = 0; i < N; i++)
    {
        if (sum + A[i] > num)
        {
            sum = A[i];
            m--;
        }
        else
        {
            sum += A[i];
        }
    }
    if (m > 0)
    {
        return 1;
    }
    return 0;
}

ll bs(ll l, ll r)
{
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return l;
}

int main()
{
    cin >> N >> K;

    ll sum = 0;
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
        sum += A[i];
    }
    cout << bs(1, sum) << endl;

    return 0;
}