| Time Limit: 1000MS | ? | Memory Limit: 65536K |
| Total Submissions: 8678 | ? | Accepted: 4288 |
Description
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
Output
Sample Input
59 237
375 743
200000 849694
2500000 8000000
Sample Output
116
28
300612
Deficit
Source
?
題意：
對于每一個月來說，如果是盈利則盈利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 |
Accepted |
164K |
0MS |
1515B |
2013-08-05 22:04:06 |
?
?
?
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
