[贪心+二分]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.

输入描述:

1
2
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.

输出描述:

1
An integer, the minimum distance of the largest step.

示例1

输入

1
2
6 3
1 3 2 2 5

输出

1
5

题意:

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

题解:

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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处。这样保证最近的两头牛之间的距离都不会比当前的最小值小,如果每个都能满足这样放就可以作为最小值。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!