转载请注明出处：優 YoU http://user.qzone.qq.com/289065406/blog/1301655498
大致题意：
给出农夫在 n 天中每天的花费，要求把这 n 天分作 m 组，每组的天数必然是连续的，要求分得各组的花费之和应该尽可能地小，最后输出各组花费之和中的最大值
解题思路：
经典的二分穷举
详细的思路我写在程序注释中，这样会更容易懂
看完我的程序还是无法切入题目的同学，建议先用 朴素的穷举 去左这题，虽然很大机会会超时，但是只是为了辅助理解。本题的二分纯粹是一个优化穷举的工具。
1
//
Memory Time
2
//
612K 297MS
3
4
#include
<
iostream
>
5
using
namespace
std;
6
7
int
n;
//
天数
8
int
m;
//
规定的分组数
9
10
/*
判断用当前的mid值能把天数n分成几组
*/
11
/*
通过比较group与m的大小，对mid值进行优化
*/
12
13
bool
judge_group(
int
mid,
int
money[])
14
{
15
int
sum
=
0
;
16
int
group
=
1
;
//
当前mid值能把n天分成的组数(初始把全部天数作为1组)
17
18
for
(
int
i
=
1
;i
<=
n;i
++
)
//
从第一天开始向下遍历每天的花费
19
if
(sum
+
money[i]
<=
mid)
//
当前i天之和<=mid时，把他们归并到一组
20
sum
+=
money[i];
21
else
//
若 前i-1天之和 加上第i天的花费 大于mid
22
{
23
sum
=
money[i];
//
则把前i-1天作为一组，第i天作为下一组的第一天
24
group
++
;
//
此时划分的组数+1
25
}
26
27
if
(group
>
m)
28
return
false
;
//
若利用mid值划分的组数比规定的组数要多，则说明mid值偏小
29
else
30
return
true
;
//
否则mid值偏大
31
}
32
33
int
main(
void
)
34
{
35
while
(cin
>>
n
>>
m)
36
{
37
int
*
money
=
new
int
[n
+
1
];
//
每天花费的金额
38
int
low
=
0
;
//
下界
39
int
high
=
0
;
//
上界
40
41
for
(
int
i
=
1
;i
<=
n;i
++
)
42
{
43
cin
>>
money[i];
44
45
high
+=
money[i];
//
把所有天数的总花费作为上界high（相当于把n天都分作1组）
46
if
(low
<
money[i])
47
low
=
money[i];
//
把n天中花费最多的那一天的花费作为下界low（相当于把n天分为n组）
48
}
//
那么要求的值必然在[low,high]范围内
49
50
int
mid
=
(low
+
high)
/
2
;
51
52
while
(low
<
high)
//
可能在low==high之前，分组数就已经=m，但是mid并不是最优，因此要继续二分
53
{
54
if
(
!
judge_group(mid,money))
55
low
=
mid
+
1
;
//
mid值偏小，下界前移
56
else
57
high
=
mid
-
1
;
//
mid值偏大，上界后移
58
59
mid
=
(low
+
high)
/
2
;
60
}
61
62
cout
<<
mid
<<
endl;
//
二分搜索最后得到的mid值必然是使得分组符合要求的最优值
63
64
delete money;
65
}
66
return
0
;
67
}
