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