`
阿尔萨斯
  • 浏览: 4108063 次
社区版块
存档分类
最新评论

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次单价才可以,那么如果单价过大ss(x1)y+1肯定是不予许的。所以对于每一个i(数量)来说,单价都有一个上限值,以保证说在增加数量的时候不会导致总价溢出。
设当前数量为i,临界总价为t,那么就有
y+1>txi
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;
}
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics