题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4803
解题报告:有一个记录器,一共有两个按钮,还有两行屏幕显示,第一行的屏幕显示的是数目,第二行的屏幕显示的是总价,按第一行的按钮表示单价不变,数量加1,同时第二行的总价会根据当前的单价进行相应的增加,然后按一下第二行的按钮表示数量不变,总价加1,这样的话单价就变大了.现在给出这个屏幕上显示的初始的第一行的是1,第二行的是1,然后再给出结束的时候第一行是x,第二行是y,让你求要从初始的变成最后的至少需要按多少次按钮,如果不能实现,那么输出-1.
很明显,当x <= y时,都是可以实现的.说明单价是大于等于1的,而我现在的单价是1,所以我现在要做的事情就是使得单价增加到现在的这个水平,然后按第二行的按钮可以使单价增加,按第一行的按钮时,单价并没有变化,所以,在整个过程中,我都要保证当前的单价乘以最终的数量的时候总价取整不会超过y,因为单价是不可以降的.有了这个条件,对于一定数量的物品,就可以得到这个数量的物品对应的总价的上限是多少了,所以中间过程只要分成按第一行的按钮还是第二行的,不需要管次数了.还要说的是,这题交C++过不了,交g++才过的.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps = 1e-;
int judge(double d)
{
return fabs(d - (int)d) < eps;
}
int main()
{
int sx,sy;
while(scanf("%d%d",&sx,&sy)!=EOF)
{
if(sx > sy)
{
printf("-1\n");
continue;
}
int ans = ;
double X = ,Y = ,p = (double)(sy + ) / sx;
while()
{
if((int)X >= sx && (int)Y >= sy) break;
//getchar();
double temp = Y / X;
if(temp < p && (int)(sx * ((Y+) / X)) <= sy)
{
int tt;
if(judge(X * p)) tt = (int)(X * p) - ;
else tt = (int)X * p;
ans += (tt - (int)Y);
Y += (double)(tt - (int)Y);
}
else
{
double t = Y / X;
X += ;
Y += t;
ans++;
}
}
printf("%d\n",ans);
}
return ;
}