轉(zhuǎn)載請(qǐng)注明出處：優(yōu) YoU http://user.qzone.qq.com/289065406/blog/1299234147
?
題意比較難懂，其實(shí)只要讀懂題意，就很簡(jiǎn)單了。
大意是一個(gè)公司在
12
個(gè)月中，或固定盈余
s
，或固定虧損
d.
但記不得哪些月盈余，哪些月虧損，只能記得連續(xù)
5
個(gè)月的代數(shù)和總是虧損
(<0
為虧損
)
，而一年中只有
8
個(gè)連續(xù)的
5
個(gè)月，分別為
1~5
，
2~6
，
…
，
8~12
問(wèn)全年是否可能盈利？若可能，輸出可能最大盈利金額，否則輸出“
Deficit".
根據(jù)經(jīng)驗(yàn)， 貪心選擇往往都在極端處（臨界點(diǎn)）選擇 。（其實(shí)這題不用貪心，單純枚舉也可以AC，因?yàn)椴煌闆r實(shí)在太少吶。。。。
不難證明，每連續(xù)
5
個(gè)月中，在保證這
5
個(gè)月經(jīng)營(yíng)之和為虧損的情況下，虧損的月數(shù)肯定應(yīng)盡量往后選，盈利的月數(shù)應(yīng)盡量往前選。證明省略。
先處理處理完
1~5
月后，剩下的月份可以根據(jù)“連續(xù)
5
個(gè)月經(jīng)營(yíng)之和為虧損”這個(gè)條件進(jìn)行確定虧損還是盈利。
本題的貪心選擇每次僅僅選取其中一種情況（
1~5
月），因?yàn)橹笤路轃o(wú)需再選擇，所以每次總共只做了一次貪心選擇。
實(shí)際上 ; 只要討論 5 種情況即可； ( 任一月固定 盈余s，或固定虧損d).
SSSSDSSSSDSS
??
4s<d
??????
保證“
連續(xù)
5
個(gè)月必虧損”，每連續(xù)
5
個(gè)月種至少
1
個(gè)月
D
，
?????????????????????????
保證可能有全年最大盈余，每連續(xù)
5
個(gè)月中至多
4
個(gè)月
S
SSSDDSSSDDSS
??
3s<2d
?????
保證“
連續(xù)
5
個(gè)月必虧損”，每連續(xù)
5
個(gè)月種至少
2
個(gè)月
D
，
保證可能有全年最大盈余，每連續(xù)
5
個(gè)月中至多
3
個(gè)月
S
SSDDDSSDDDSS
??
2s<3d
?????
保證“
連續(xù)
5
個(gè)月必虧損”，每連續(xù)
5
個(gè)月種至少
3
個(gè)月
D
，
保證可能有全年最大盈余，每連續(xù)
5
個(gè)月中至多
2
個(gè)月
S
SDDDDSDDDDSD
??
s<4d
??????
保證“
連續(xù)
5
個(gè)月必虧損”，每連續(xù)
5
個(gè)月種至少
4
個(gè)月
D
，
保證可能有全年最大盈余，每連續(xù)
5
個(gè)月中至多
1
個(gè)月
S
DDDDDDDDDDDD
??
s>=4d
?????
保證“
連續(xù)
5
個(gè)月必虧損”，每連續(xù)
5
個(gè)月種至少
5
個(gè)月
D
，
每月虧損，此情況全年必虧損
要注意的是，前
4
種情況都僅僅是“可能有全年的盈余”，而不是“一定有全年的盈余”。
但是若果一旦有盈余，必定是最大盈余
把
5
種情況可以歸納為關(guān)于
s
的判定條件：
0 <= s <1/4d
??????????
每連續(xù)
5
個(gè)月種至少
1
個(gè)月
D
1/4d <= s < 2/3d
?????????
每連續(xù)
5
個(gè)月種至少
2
個(gè)月
D
2/3d <= s < 3/2d
?????????
每連續(xù)
5
個(gè)月種至少
3
個(gè)月
D
3/2d <= s < 4d
??????????
每連續(xù)
5
個(gè)月種至少
4
個(gè)月
D
4d <= s
???????????????
全年各月必虧損
ps:
輸入要在注意終止條件為
while(cin>>s>>d)
?
1
//
Memory Time
2
//
256K 16MS
3
4
5
#include
<
iostream
>
6
using
namespace
std;
7
8
int
main(
void
)
9
{
10
double
s,d;
11
while
(cin
>>
s
>>
d)
12
{
13
bool
flag
=
false
;
14
int
surplus
=
0
;
15
if
(s
>=
4
*
d)
16
flag
=
true
;
17
18
else
if
((s
>=
1.5
*
d)
&&
(s
<
4
*
d))
19
{
20
surplus
=
3
*
s
-
9
*
d;
21
if
(surplus
<
0
)
22
flag
=
true
;
23
}
24
25
else
if
((s
>=
0.666666
*
d)
&&
(s
<
1.5
*
d))
26
{
27
surplus
=
6
*
(s
-
d);
28
if
(surplus
<
0
)
29
flag
=
true
;
30
}
31
32
else
if
((s
>=
0.25
*
d)
&&
(s
<
0.666666
*
d))
33
{
34
surplus
=
8
*
s
-
4
*
d;
35
if
(surplus
<
0
)
36
flag
=
true
;
37
}
38
39
else
if
((s
>=
0
)
&&
(s
<
0.25
*
d))
40
{
41
surplus
=
10
*
s
-
2
*
d;
42
if
(surplus
<
0
)
43
flag
=
true
;
44
}
45
46
if
(flag)
47
cout
<<
"
Deficit
"
<<
endl;
48
else
49
cout
<<
surplus
<<
endl;
50
}
51
return
0
;
52
}
更多文章、技術(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ì)您有幫助就好】元
