首页 > 代码库 > HDU 4803 Poor Warehouse Keeper

HDU 4803 Poor Warehouse Keeper

2024-08-04 04:59:56   210人阅读

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4803

解题报告:有一个记录器,一共有两个按钮,还有两行屏幕显示,第一行的屏幕显示的是数目,第二行的屏幕显示的是总价,按第一行的按钮表示单价不变,数量加1,同时第二行的总价会根据当前的单价进行相应的增加,然后按一下第二行的按钮表示数量不变,总价加1,这样的话单价就变大了.现在给出这个屏幕上显示的初始的第一行的是1,第二行的是1,然后再给出结束的时候第一行是x,第二行是y,让你求要从初始的变成最后的至少需要按多少次按钮,如果不能实现,那么输出-1.

很明显,当x <= y时,都是可以实现的.说明单价是大于等于1的,而我现在的单价是1,所以我现在要做的事情就是使得单价增加到现在的这个水平,然后按第二行的按钮可以使单价增加,按第一行的按钮时,单价并没有变化,所以,在整个过程中,我都要保证当前的单价乘以最终的数量的时候总价取整不会超过y,因为单价是不可以降的.有了这个条件,对于一定数量的物品,就可以得到这个数量的物品对应的总价的上限是多少了,所以中间过程只要分成按第一行的按钮还是第二行的,不需要管次数了.还要说的是,这题交C++过不了,交g++才过的.

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const double eps = 1e-6; 8 int judge(double d) 9 {10     return fabs(d - (int)d) < eps;11 }12 int main()13 {14     int sx,sy;15     while(scanf("%d%d",&sx,&sy)!=EOF)16     {17         if(sx > sy)18         {19             printf("-1\n");20             continue;21         }22         int ans = 0;23         double X = 1,Y = 1,p = (double)(sy + 1) / sx;24         while(1)25         {26             if((int)X >= sx && (int)Y >= sy) break;27             //getchar();28             double temp = Y / X;29             if(temp < p && (int)(sx * ((Y+1) / X)) <= sy)30             {31                 int tt;32                 if(judge(X * p)) tt = (int)(X * p) - 1;33                 else tt = (int)X * p;34                 ans += (tt - (int)Y);35                 Y += (double)(tt - (int)Y);36             }37             else38             {39                 double t = Y / X;40                 X += 1;41                 Y += t;42                 ans++;43             }44         }45         printf("%d\n",ans);46     }47     return 0;48 }
View Code

 

HDU 4803 Poor Warehouse Keeper


联系
我们