Posted on 2011-01-23 13:34
Onway 閱讀(384)
評論(0) 編輯 收藏 引用 所屬分類:
傷不起的ACM
/*
題意：還是直接貼上discuss里別人給出的吧：
對于每一個月來說，是盈利如果則盈利S，如果虧空則虧d。
每五個月進(jìn)行一次統(tǒng)計，共統(tǒng)計八次（1-5月一次，2-6月一次
.）
統(tǒng)計的結(jié)果是這八次都是虧空。
問題：判斷全年是否能盈利，如果能則求出最大的盈利。
如果不能盈利則輸出Deficit
類型：貪心
思路：為了使得盈利最大，一次統(tǒng)計的五個月里，應(yīng)該盡量使得s出現(xiàn)最多，而為了保證每一次統(tǒng)計都是虧空，顯然一次統(tǒng)計的五個月里，s不能出現(xiàn)五次。如果s能出現(xiàn)四次的話，為了保證虧空，應(yīng)該有4*s<d，如果能出現(xiàn)3次，則應(yīng)有3*s<2d……以此類推。當(dāng)s>=4d的時候，即只要有一個s出現(xiàn)，都不能滿足統(tǒng)計虧空條件的時候，只能讓其出現(xiàn)五個d了。在以上分析中，為了讓d的出現(xiàn)盡可能的少，顯然，一個d應(yīng)該盡可能的跟大家（其他統(tǒng)計）“共享”,即對于第一次統(tǒng)計，s如果能出現(xiàn)，則讓其出現(xiàn)在最前。以后各次統(tǒng)計，不到“萬不得意”，不讓d出現(xiàn)。
后記：看不懂英文題意，直覺discuss肯定有講題意的，上去一題果然。而后覺得直接暴力能暴出來，寫出來超時，從時間復(fù)雜度來看，我始終不懂為何超時，盡管我沒有去剪枝。十二個月，每個月只能出現(xiàn)盈利或虧損，則有2^12=4096種情況，對于每一種情況，要判斷是否能使8次統(tǒng)計虧空，進(jìn)行8＊5次運算，從符合條件的情況中取出最大值并判斷盈利或虧空。
然后，上discuss看了一下別人的提示，想到了上述思路，其實跟人家的已經(jīng)是大同小異了。題意是看別人的，解題精華是看別人的，這個題目算是做得失敗了。
*/
#include <cstring>
#include <iostream>
using namespace std;
char seq[14];
int main()
{
int s,d;
while(cin>>s>>d)
{
int sum=0;
if(4s<d) sum=10*s-2*d;
else if(3*s<2*d) sum=8*s-4*d;
else if(2*s<3*d) sum=6*s-6*d;
else if(s<4*d) sum=3*s-9*d;
else
{
cout<<"Deficit"<<endl;
continue;
}
if(sum<0) cout<<"Deficit"<<endl;
else
cout<<sum<<endl;
}
return 0;
}