Posted on 2011-01-23 13:34
Onway 阅读(326)
评论(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;
}