Description

Input

Output

Sample Input

59 237

375 743

200000 849694

2500000 8000000

Sample Output

116

28

300612

Deficit

Source

Waterloo local 2000.01.29

题意：

对于每一个月来说，如果是盈利则盈利S，如果亏空则亏d。

每五个月进行一次统计，共统计八次（1-5月一次，2-6月一次.......）

统计的结果是这八次都是亏空。

问题：判断全年是否能盈利，如果能则求出最大的盈利。

如果不能盈利则输出Deficit

分析：

我是先在草稿纸上枚举了一下前两种情况。然后就有了思路。

贪心的思想，8次统计，每次统计报账都是亏损，但是要全年盈利最大，只要每次统计的亏损值最小就可以了。也就是说每次统计的5个月中，盈利的月要尽可能多。

故：

1、用一个数组q1向后判断，一个队列q2把每次确定的12个月各月的盈利和亏损情况存起来。

2、init()函数是用来确定前5个月每个月的盈利和亏损情况的。为了保证盈利的月尽可能多且枚举的次数小，从5个月中4个月盈利到1个月盈利依次枚举，算5个月的总和是否

     小于0满足亏损。找到了就存进q1和q2并返回true.找不到返回false,全年则只有亏损的份了。

3、judge()是每次利用之前确定的后四个月的盈利亏损情况向后确定接下来的一个月的盈利亏损情况。例如：已经知道了1、2、3、4、5个月的盈利亏损情况。当要确定第6

     个月的情况时，因为2—6月5个月报账，先把2、3、4、5的总账加起来，如果6月盈余加上去满足这5个月亏损，则6月盈余可以使全年的总值尽量大。依次类推。

4、compute()是来算存在q2里全年是盈利还是亏损的。

贪心思想----->子问题局部最优。

感想：

开始sum忘了清0导致第5组测试数据老过不了啊，拙计~！

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

int s,d;

queue<int> q2;

int q1[100000];

int head,rear;

bool init()

{

    int i,j,k;

    head=0,rear=0;

    for(i=4;i>=1;i--)

    {

        if(s*i-d*(5-i)<0)

        {

            for(j=0;j<i;j++)

            {

                q1[j]=s;

                rear++;

                q2.push(s);

            }

            for(k=i;k<5;k++)

            {

                q1[k]=-d;

                rear++;

                q2.push(-d);

            }

            return true;

        }

    }

    return false;

}

int compute()

{

    int sum=0;

    while(!q2.empty())

    {

        //printf("%d\n",q2.front());

        sum+=q2.front();

        q2.pop();

    }

    return sum;

}

void judge()

{

    int j;

    int sum;

    for(int i=0;i<7;i++)

    {

        head++;

        sum=0;

        for(j=head;j<rear;j++)

            sum+=q1[j];

		//printf("test: %d\n",sum+s);

        if(sum+s>=0)

        {

            q1[rear++]=-d;

            q2.push(-d);

        }

        else

        {

            q1[rear++]=s;

            q2.push(s);

        }

    }

}

int main()

{

    int leaf;

    while(scanf("%d%d",&s,&d)!=EOF)

    {

        while(!q2.empty())

            q2.pop();

        leaf=init();

        judge();

        int s=compute();

        if(s<0||leaf==false)

            printf("Deficit\n");

        else printf("%d\n",s);

    }

    return 0;

}