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

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條評論
主站蜘蛛池模板: 亚洲高清成人 | 麻豆国产精品免费视频 | 久久中文字幕一区二区 | 亚洲图片综合 | 日韩成人| 91在线视| 色sese| 国产日韩欧美91 | 99国产精品视频免费观看 | 久久色精品 | 国产精品香蕉在线观看不卡 | 免费一级欧美大片视频在线 | 男女精品视频 | julia中文在线| 久久婷婷人人澡人人爱91 | 国产在播放一区 | 在线精品视频成人网 | 久久96国产精品久久久 | 国产精品乱码免费一区二区 | 亚洲 欧美 日韩 在线 | 久久93精品国产91久久综合 | 婷婷免费高清视频在线观看 | 91精彩视频在线观看 | 老司机久久影院 | 久久婷婷五色综合夜啪 | 久久综合久久综合九色 | 一级片免费视频 | 按摩理论片| 久热这里只精品热在线观看 | 欧美国产日韩久久久 | 亚洲欧美韩国 | 97夜夜操| 久久精品视频免费播放 | 色婷婷综合久久久 | 爱久久www.35669 | 久久久国产在线 | 亚洲国产天堂在线网址 | 这里只有精品在线 | 久久99精品久久久久久国产人妖 | 亚洲一区二区三区在线播放 | 色婷婷综合在线视频最新 |