poj2586 Y2K Accounting Bug 贪心

 1 ///2014.3.3
 2 ///poj2586
 3 
 4 /**
 5  *题目大意是一个公司在12个月中，或固定盈余s，或固定亏损d.
 6  *但记不得哪些月盈余，哪些月亏损，

 7  *只能记得连续5个月的代数和总是亏损(<0为亏损)，
 8  *问全年是否可能盈利，若可能，输出可能最大盈利金额，
 9  *否则输出“Deficit”.
10  *思路：
11  *题意说连续的五个月的代数总和一定是亏损，则可以根据 s 和 d
12  *求出连续的五个月至少有 dInFive 个月是亏损的
13  *例如连续的五个月至少有 2 个月亏损（dInFive=2）
14  *则，1-5月中4月和5月设为亏损，接着检查下一个连续的五个月（2-6月）
15  *从尾部开始将其设成一共有2个月亏损
16  *最后可以求出12个月中一共至少要有几个月亏损
17  */
18 
19 #include <cstdio>
20 
21 int s,d;
22 int dInFive;   ///表示在连续五个月中最少有几个月份亏损
23 int month[6] = {0,2,4,6,9,12}; 
24 ///month[i]表示 i 为 dInFive时，12个月中的最少亏损月份数，笔算即可求出
25 int S;
26 
27 void init( )
28 {
29     for(dInFive=0 ; dInFive*d<(5-dInFive)*s ; dInFive++); ///求出dInFive
30     S = s*(12-month[dInFive]) - d*month[dInFive];
31 }
32 
33 int main( )
34 {
35 //    freopen("in","r",stdin);
36 //    freopen("out","w",stdout);
37 
38     while( scanf("%d%d",&s,&d)!=EOF ){
39         init();
40         if( S>0 )
41             printf("%d\n",S);
42         else
43             printf("Deficit\n");
44     }
45     return 0;
46 }