hdu 4803 Poor Warehouse Keeper(贪心+数学)

本文主要是介绍hdu 4803 Poor Warehouse Keeper(贪心+数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4803 Poor Warehouse Keeper

题目大意：有以个屏幕可以显示两个值，一个是数量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;
}