轉(zhuǎn)載請(qǐng)注明出處：優(yōu) YoU http://user.qzone.qq.com/289065406/blog/1301655498
?
大致題意：
給出農(nóng)夫在 n 天中每天的花費(fèi)，要求把這 n 天分作 m 組，每組的天數(shù)必然是連續(xù)的，要求分得各組的花費(fèi)之和應(yīng)該盡可能地小，最后輸出各組花費(fèi)之和中的最大值
解題思路：
經(jīng)典的二分窮舉
詳細(xì)的思路我寫(xiě)在程序注釋中，這樣會(huì)更容易懂
看完我的程序還是無(wú)法切入題目的同學(xué)，建議先用 樸素的窮舉 去左這題，雖然很大機(jī)會(huì)會(huì)超時(shí)，但是只是為了輔助理解。本題的二分純粹是一個(gè)優(yōu)化窮舉的工具。
1
//
Memory Time
2
//
612K 297MS
3
4
#include
<
iostream
>
5
using
namespace
std;
6
7
int
n;
//
天數(shù)
8
int
m;
//
規(guī)定的分組數(shù)
9
10
/*
判斷用當(dāng)前的mid值能把天數(shù)n分成幾組
*/
11
/*
通過(guò)比較group與m的大小，對(duì)mid值進(jìn)行優(yōu)化
*/
12
13
bool
judge_group(
int
mid,
int
money[])
14
{
15
int
sum
=
0
;
16
int
group
=
1
;
//
當(dāng)前mid值能把n天分成的組數(shù)(初始把全部天數(shù)作為1組)
17
18
for
(
int
i
=
1
;i
<=
n;i
++
)
//
從第一天開(kāi)始向下遍歷每天的花費(fèi)
19
if
(sum
+
money[i]
<=
mid)
//
當(dāng)前i天之和<=mid時(shí)，把他們歸并到一組
20
sum
+=
money[i];
21
else
//
若 前i-1天之和 加上第i天的花費(fèi) 大于mid
22
{
23
sum
=
money[i];
//
則把前i-1天作為一組，第i天作為下一組的第一天
24
group
++
;
//
此時(shí)劃分的組數(shù)+1
25
}
26
27
if
(group
>
m)
28
return
false
;
//
若利用mid值劃分的組數(shù)比規(guī)定的組數(shù)要多，則說(shuō)明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
];
//
每天花費(fèi)的金額
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];
//
把所有天數(shù)的總花費(fèi)作為上界high（相當(dāng)于把n天都分作1組）
46
if
(low
<
money[i])
47
low
=
money[i];
//
把n天中花費(fèi)最多的那一天的花費(fèi)作為下界low（相當(dāng)于把n天分為n組）
48
}
//
那么要求的值必然在[low,high]范圍內(nèi)
49
50
int
mid
=
(low
+
high)
/
2
;
51
52
while
(low
<
high)
//
可能在low==high之前，分組數(shù)就已經(jīng)=m，但是mid并不是最優(yōu)，因此要繼續(xù)二分
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值必然是使得分組符合要求的最優(yōu)值
63
64
delete money;
65
}
66
return
0
;
67
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
