首页 > ACM题库 > HDU-杭电 > HDU 4803-Poor Warehouse Keeper-贪心-[解题报告]HOJ
2015
09-18

HDU 4803-Poor Warehouse Keeper-贪心-[解题报告]HOJ

Poor Warehouse Keeper

问题描述 :

Jenny is a warehouse keeper. He writes down the entry records everyday. The record is shown on a screen, as follow:
GPA

There are only two buttons on the screen. Pressing the button in the first line once increases the number on the first line by 1. The cost per unit remains untouched. For the screen above, after the button in the first line is pressed, the screen will be:
GPA

The exact total price is 7.5, but on the screen, only the integral part 7 is shown.
Pressing the button in the second line once increases the number on the second line by 1. The number in the first line remains untouched. For the screen above, after the button in the second line is pressed, the screen will be:
GPA

Remember the exact total price is 8.5, but on the screen, only the integral part 8 is shown.
A new record will be like the following:
GPA

At that moment, the total price is exact 1.0.
Jenny expects a final screen in form of:
GPA

Where x and y are previously given.
What’s the minimal number of pressing of buttons Jenny needs to achieve his goal?

输入:

There are several (about 50, 000) test cases, please process till EOF.
Each test case contains one line with two integers x(1 <= x <= 10) and y(1 <= y <= 109) separated by a single space – the expected number shown on the screen in the end.

输出:

There are several (about 50, 000) test cases, please process till EOF.
Each test case contains one line with two integers x(1 <= x <= 10) and y(1 <= y <= 109) separated by a single space – the expected number shown on the screen in the end.

样例输入:

1 1
3 8
9 31

样例输出:

0
5
11

Hint
For the second test case, one way to achieve is: (1, 1) -> (1, 2) -> (2, 4) -> (2, 5) -> (3, 7.5) -> (3, 8.5)

题目链接: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;
}

参考:http://blog.csdn.net/keshuai19940722/article/details/26005267