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

?

題意：

    對(duì)于每一個(gè)月來(lái)說(shuō)，如果是盈利則盈利S，如果虧空則虧d。

每五個(gè)月進(jìn)行一次統(tǒng)計(jì)，共統(tǒng)計(jì)八次（1-5月一次，2-6月一次.......）

統(tǒng)計(jì)的結(jié)果是這八次都是虧空。

問(wèn)題：判斷全年是否能盈利，如果能則求出最大的盈利。

如果不能盈利則輸出Deficit
  

?

分析：

我是先在草稿紙上枚舉了一下前兩種情況。然后就有了思路。

貪心的思想，8次統(tǒng)計(jì)，每次統(tǒng)計(jì)報(bào)賬都是虧損，但是要全年盈利最大，只要每次統(tǒng)計(jì)的虧損值最小就可以了。也就是說(shuō)每次統(tǒng)計(jì)的5個(gè)月中，盈利的月要盡可能多。

故：

1、用一個(gè)數(shù)組q1向后判斷，一個(gè)隊(duì)列q2把每次確定的12個(gè)月各月的盈利和虧損情況存起來(lái)。

2、init()函數(shù)是用來(lái)確定前5個(gè)月每個(gè)月的盈利和虧損情況的。為了保證盈利的月盡可能多且枚舉的次數(shù)小，從5個(gè)月中4個(gè)月盈利到1個(gè)月盈利依次枚舉，算5個(gè)月的總和是否

???? 小于0滿足虧損。找到了就存進(jìn)q1和q2并返回true.找不到返回false,全年則只有虧損的份了。

3、judge()是每次利用之前確定的后四個(gè)月的盈利虧損情況向后確定接下來(lái)的一個(gè)月的盈利虧損情況。例如：已經(jīng)知道了1、2、3、4、5個(gè)月的盈利虧損情況。當(dāng)要確定第6

?????個(gè)月的情況時(shí)，因?yàn)?—6月5個(gè)月報(bào)賬，先把2、3、4、5的總賬加起來(lái)，如果6月盈余加上去滿足這5個(gè)月虧損，則6月盈余可以使全年的總值盡量大。依次類推。

4、compute()是來(lái)算存在q2里全年是盈利還是虧損的。

貪心思想----->子問(wèn)題局部最優(yōu)。

感想：

開(kāi)始sum忘了清0導(dǎo)致第5組測(cè)試數(shù)據(jù)老過(guò)不了啊，拙計(jì)~！

?

代碼：

    #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;

}




  

?

?

?

?

?

?

?

poj 2586 Y2K Accounting Bug (貪心)