第十四届华中科技大学程序设计竞赛 K--Walking in the Forest

链接：https://www.nowcoder.com/acm/contest/106/K
来源：牛客网

题目描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

Now you're going to walk through a large forest. There is a path consisting of N stones winding its way to the other side of the forest. Between every two stones there is a distance. Let d_iindicates the distance between the stone i and i+1.Initially you stand at the first stone, and your target is the N-th stone. You must stand in a stone all the time, and you can stride over arbitrary number of stones in one step. If you stepped from the stone i to the stone j, you stride a span of (d_i+d_i+1+...+d_j-1). But there is a limitation. You're so tired that you want to walk through the forest in no more than K steps. And to walk more comfortably, you have to minimize the distance of largest step.

输入描述:

The first line contains two integer N and K as described above.
Then the next line N-1 positive integer followed, indicating the distance between two adjacent stone.

输出描述:

An integer, the minimum distance of the largest step.

输入例子:

6 3

1 3 2 2 5

输出例子:

-->

示例1

输入

6 3

1 3 2 2 5

输出

5

题解：
二分答案（好蠢啊）

/*

    data:2018.5.22

    author:gsw

    link:https://www.nowcoder.com/acm/contest/106/K

*/

#define ll long long

#define IO ios::sync_with_stdio(false);

#include<math.h>

#include<stdio.h>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define maxn 100005

ll l,r,mid;

int n,k;

ll dis[maxn];

bool judge(ll d)

{

    ll tem=;int kk=;

    for(int i=;i<n-;i++)

    {

        if(dis[i]>d)return false;

        if(tem+dis[i]>d)

        {

            tem=dis[i];

            kk++;

        }

        else tem+=dis[i];

    }

    kk++;

    if(kk>k)return false;

    return true;

}

int main()

{

    l=r=;

    scanf("%d%d",&n,&k);

    for(int i=;i<n-;i++)

    {

        scanf("%lld",&dis[i]);

        r+=dis[i];

    }ll mid=;

    while(l<r-)

    {

        mid=(l+r)>>;

        if(judge(mid))r=mid;

        else l=mid;

    }

    printf("%lld\n",r);

    return ;

}