Walking in the Forest （二分~最小化最大值）

题目描述

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 _i indicates 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.

                    这道题就是一道二分~最小化最大值的模板题~~

                   到时要注意几个细节~~：

                   1.sum会爆int ；

                   2. 用li < ri 的情况下可能会使最后的不经过检测；

                   3.li初始化为1，而又没有考虑一步不能跨过的情况；

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
long long int m[100005];	
int n, k;
int check(long long int mid)
{
	long long int sum = 0;
	int cnt = 1;
	for (int s = 0; s < n; s++)
	{
		if (m[s] > mid)
		{
			return 0;
		}
		sum += m[s];
		if (sum > mid)
		{
			sum = m[s];
			cnt++;
		}
	}
	if (cnt > k)
	{
		return 0;
	}
	return 1;
}
int main()
{
	cin >> n >> k;
	n--;
	long long int sum = 0;
	for (int s = 0; s < n; s++)
	{
		scanf("%lld", &m[s]);
		sum += m[s];
	}
	long long int ans = sum;
	long long int li = 0, ri = sum;
	while (li <= ri)
	{
		long long int mid = (li + ri) / 2;
		if (check(mid))
		{
		    ans = mid;
			ri = mid - 1;
		}
		else
		{
             li = mid+1;
		}
	}
	cout << ans << endl;
	return 0;
}