轉載請注明出處：優 YoU http://user.qzone.qq.com/289065406/blog/1299234147
?
題意比較難懂，其實只要讀懂題意，就很簡單了。
大意是一個公司在
12
個月中，或固定盈余
s
，或固定虧損
d.
但記不得哪些月盈余，哪些月虧損，只能記得連續
5
個月的代數和總是虧損
(<0
為虧損
)
，而一年中只有
8
個連續的
5
個月，分別為
1~5
，
2~6
，
…
，
8~12
問全年是否可能盈利？若可能，輸出可能最大盈利金額，否則輸出“
Deficit".
根據經驗， 貪心選擇往往都在極端處（臨界點）選擇 。（其實這題不用貪心，單純枚舉也可以AC，因為不同情況實在太少吶。。。。
不難證明，每連續
5
個月中，在保證這
5
個月經營之和為虧損的情況下，虧損的月數肯定應盡量往后選，盈利的月數應盡量往前選。證明省略。
先處理處理完
1~5
月后，剩下的月份可以根據“連續
5
個月經營之和為虧損”這個條件進行確定虧損還是盈利。
本題的貪心選擇每次僅僅選取其中一種情況（
1~5
月），因為之后月份無需再選擇，所以每次總共只做了一次貪心選擇。
實際上 ; 只要討論 5 種情況即可； ( 任一月固定 盈余s，或固定虧損d).
SSSSDSSSSDSS
??
4s<d
??????
保證“
連續
5
個月必虧損”，每連續
5
個月種至少
1
個月
D
，
?????????????????????????
保證可能有全年最大盈余，每連續
5
個月中至多
4
個月
S
SSSDDSSSDDSS
??
3s<2d
?????
保證“
連續
5
個月必虧損”，每連續
5
個月種至少
2
個月
D
，
保證可能有全年最大盈余，每連續
5
個月中至多
3
個月
S
SSDDDSSDDDSS
??
2s<3d
?????
保證“
連續
5
個月必虧損”，每連續
5
個月種至少
3
個月
D
，
保證可能有全年最大盈余，每連續
5
個月中至多
2
個月
S
SDDDDSDDDDSD
??
s<4d
??????
保證“
連續
5
個月必虧損”，每連續
5
個月種至少
4
個月
D
，
保證可能有全年最大盈余，每連續
5
個月中至多
1
個月
S
DDDDDDDDDDDD
??
s>=4d
?????
保證“
連續
5
個月必虧損”，每連續
5
個月種至少
5
個月
D
，
每月虧損，此情況全年必虧損
要注意的是，前
4
種情況都僅僅是“可能有全年的盈余”，而不是“一定有全年的盈余”。
但是若果一旦有盈余，必定是最大盈余
把
5
種情況可以歸納為關于
s
的判定條件：
0 <= s <1/4d
??????????
每連續
5
個月種至少
1
個月
D
1/4d <= s < 2/3d
?????????
每連續
5
個月種至少
2
個月
D
2/3d <= s < 3/2d
?????????
每連續
5
個月種至少
3
個月
D
3/2d <= s < 4d
??????????
每連續
5
個月種至少
4
個月
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
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
