轉載請注明出處：優 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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
