[贪心+二分]HUST-Walking in the Forest+POJ-疯牛（求最小化最大值最大化最小值两道经典例题）

今天刚好做了一道关于最大值最小化的问题，这类问题的基本思路就是二分加贪心。那就针对该类问题举两道经典例题进行总结吧。

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 di 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 (di+di+1+…+dj-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

输入

6 3
1 3 2 2 5

输出

5

题意：

有n颗石子，每相邻两颗石子间又一个距离，因此n颗石子共有n-1段距离。现在要求你最多用k步从第一颗石子跳到最后一颗石子。现在让你求最大的一步至少需要跨多少距离。

题解：

典型的最大值最小化问题。用贪心+二分解决即可。先选取一个标准值，然后从第一颗石子往后距离相加，如果加了之后大于标准值，则步数stemp加一，距离清零。最后比较stemp是否小于等于k值。标准值的范围在相邻石子距离最大值ld与第一颗石子到最后一颗石子距离之间rd，因此每次选取中间值作为标准，如果stemp>k，右边界限rd=mid-1，否则ld=mid+1。但需注意有组样例过大容易超时，因此尽量用long long代替int。

代码：

#include<stdio.h>
long long  a[100010];
int n, k;
bool check(long long ld,long long rd,long long mind) {
	long long cnt = 0;
	int stemp = 1;
	for (int i = 0; i < n - 1; i++) {
		if (cnt + a[i] <= mind) {
			cnt += a[i];
		}
		else {
			cnt = a[i];
			stemp++;
		}
		if (stemp > k)
			return false;
	}
	if (stemp <= k)
		return true;
	return false;
}
int main() {
	while (~scanf("%d%d", &n, &k)) {
		long long maxn = 0, sumn = 0;
		for (int i = 0; i < n - 1; i++) {
			scanf("%lld", &a[i]);
			sumn += a[i];
			if (maxn < a[i])
				maxn = a[i];
		}
		long long ld = maxn;
		long long rd = sumn;
		long long mind = (ld + rd) / 2;
		while (ld <= rd) {
			bool flag = check(ld, rd, mind);
			if (!flag) {
				ld = mind + 1;
				mind = (ld + rd) / 2;
			}
			else {
				rd = mind - 1;
				mind = (ld + rd) / 2;
			}
		}
		printf("%lld\n", ld);
	}
	return 0;
}

POJ2456疯牛 （最小值最大化例题）

时间限制：1000 ms | 内存限制：65535 KB

难度：4

• 描述

  农夫 John 建造了一座很长的畜栏，它包括N (2 <= N <= 100,000)个隔间，这些小隔间依次编号为x1,…,xN (0 <= xi <= 1,000,000,000).但是，John的C (2 <= C <= N)头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是什么呢？输入有多组测试数据，以EOF结束。第一行：空格分隔的两个整数N和C第二行——第N+1行：分别指出了xi的位置输出每组测试数据输出一个整数，满足题意的最大的最小值，注意换行。样例输入5 312849样例输出3

题意：有n个牛栏，选m个放进牛，相当于一条线段上有 n 个点，选取 m 个点，使得相邻点之间的最小距离值最大。

题解：首先给出n个牛棚的位置，那么每个牛棚之间的最小距离是和相邻两个牛棚之间的距离。因此，先给牛棚的位置排个序。将第一头牛放在0号位置，二分法不断缩进距离d，如果前一头牛放到了xi处，就要将下一头放到满足xi+d<=xj的最小的xj处。这样保证最近的两头牛之间的距离都不会比当前的最小值小，如果每个都能满足这样放就可以作为最小值。

代码：

#include<iostream>  
#include<algorithm>  
using namespace std;  
int v[100005];  
int n, c;  
int check(int d) {  
    int tmp = v[0], cnt = 1;  
    for (int i = 1; i < n; i++) {  
        if (v[i] - tmp >= d) {  
            cnt++;  
            tmp = v[i];  
        }  
    }  
    if (cnt >= c)  
        return 1;  
    return 0;  
}  
int main() {  
    while (cin >> n >> c) {  
        for (int i = 0; i < n; i++)  
            cin >> v[i];  
        sort(v, v + n);  
        int l = 0, r = v[n - 1], mid;  
        while (l <= r) {  
            mid = (l + r) / 2;  
            if (check(mid))  
                l = mid + 1;  
            else  
                r = mid - 1;  
        }  
        printf("%d\n", r);  
    }  
    return 0;  
}