题目大意:有以个屏幕可以显示两个值,一个是数量x,一个是总价y。有两种操作,一种是加一次总价,变成x,x+y;一种是加一个数量,这要的话总价也会相应加上一个的价钱,变成x+1,y+y/x。总价显示的为取整后的整数,小数部分忽略。给定一个目标x,y,初始状态为1,1,求最少需要多少次可以目标状态,不可以达到的话输出-1.
解题思路:如果是加一次总价的话,单价就在变大;如果是加一次数量的话,单价是不变的。总而言之,单价是只会往上涨,而不会往下降的。
然后物品的数量也必须从1变成x,也就是说至少要加x-1次单价才可以,那么如果单价过大s,s∗(x−1)≥y+1肯定是不予许的。所以对于每一个i(数量)来说,单价都有一个上限值,以保证说在增加数量的时候不会导致总价溢出。
设当前数量为i,临界总价为t,那么就有
y+1>t∗xi
t<(y+1)∗ix
即,每次对于一个数量,尽量加总价,使得单价尽量大,并且保证在和面加数量时不会大于上限,因为单价大的话,加一次数量总价接近目标值的速度会更快。
#include <cstdio>
#include <cstring>
#include <cmath>
const double eps = 1e-9;
int main () {
double x, y;
while (scanf("%lf%lf", &x, &y) == 2) {
if (x > y) {
printf("-1\n");
continue;
}
double k = (y+1-eps) / x;
int cnt = (int)x - 1;
double tmp = 1;
for (int i = 1; i <= (int)x; i++) {
double t = i * k;
int u = (int)(t-tmp);
tmp += u;
tmp = tmp * (i+1) / i;
cnt += u;
}
printf("%d\n", cnt);
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
acm hdu as easy as a+b
【HDU 3993】田忌赛马 题解+勘误 题解这里就略写一下了,主要是勘误。 这道题是2011年之前的多校训练题,2020年的今天,我们一个集训队全部挂在上面了。最后在HDU看到了9年前的讨论区,才知道这题有如下问题: speed...
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电OnlineJudge 200-2099的解题报告
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
杭电ACM课件2014版之 (HDUACM201403版_03)贪心算法
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
杭电ACM课件2014版之 (HDUACM201403版_02)简单数学题
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门