亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

poj 2586 Y2K Accounting Bug (貪心)

系統 2721 0
Y2K Accounting Bug
Time Limit: 1000MS ? Memory Limit: 65536K
Total Submissions: 8678 ? Accepted: 4288

Description

Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc.
All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite.

Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post.

Input

Input is a sequence of lines, each containing two positive integers s and d.

Output

For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible.

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;

}




  


?

11927011

fukan

2586

Accepted

164K

0MS

C++

1515B

2013-08-05 22:04:06

?

?

?

?

?

?

poj 2586 Y2K Accounting Bug (貪心)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久免费毛片 | 久热这里只有精品99国产6 | 一级理论片免费观看在线 | 婷婷在线视频国产综合 | 操一操日一日 | 99久久国内精品成人免费 | 337p欧洲日本大胆艺术 | 国产中文字幕在线免费观看 | 久草性视频 | 国产精品日韩欧美一区二区 | 亚洲午夜综合网 | 美女视频很黄很暴黄是免费的 | 四房快播 | 成人精品一区二区久久久 | 日韩精品欧美高清区 | 奇米成人| 在线500福利视频国产 | 欧美三级在线观看不卡视频 | 全免费一级毛片在线播放 | 久久毛片免费看一区二区三区 | 天天综合网在线 | 亚洲国产aaa毛片无费看 | 99热播在线观看 | 亚洲欧美激情综合第一区 | 91大神在线精品视频一区 | 曰鲁夜鲁鲁狠狠综合 | 国产精品资源站 | 美女操穴 | 国产在视频线在精品 | 91亚洲国产成人久久精品网站 | 中文字幕区 | 欧美毛片大全 | 国产h片在线观看 | 亚洲婷婷丁香 | 成人毛片全部免费观看 | 久久这里只有 | 动漫三级在线观看 | 精品欧美一区二区三区 | 亚洲精品成人网久久久久久 | 日本一级片网站 | 国产精品久久现线拍久青草 |