hdu 4803 Poor Warehouse Keeper（贪心）

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

hdu 4803 Poor Warehouse Keeper（贪心）

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

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:

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:

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:

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

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

Input

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 <= 10 ⁹) separated by a single space - the expected number shown on the screen in the end.

Output

For each test case, print the minimal number of pressing of the buttons, or “-1”(without quotes) if there’s no way to achieve his goal.

Sample Input

1 1
3 8
9 31

Sample Output

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)

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

    即，每次对于一个数量，尽量加总价，使得单价尽量大，并且保证在和面加数量时不会大于上限，因为单价大的话，加一次数量总价接近目标值的速度会更快。

比赛的时候没写出来，后来看了题解才交了上去，用cin会tle。。。

//
//  main.cpp
//  160929
//
//  Created by 刘哲 on 17/4/13.
//  Copyright © 2016年 my_code. All rights reserved.
//
//#include <bits/stdc++.h>#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#define lowbit(x) (x&-x)
using namespace std;
#define ll long long
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int main()
{double x,y;while(~scanf("%lf%lf",&x,&y)){if(x>y){puts("-1");continue;}double k = (y+0.99999)/x;int ans = x-1;double tmp = 1.0;for(int i=1;i<=int(x);i++){double t=i*k;int up=int(t-tmp);tmp += up;tmp=tmp*(i+1)/i;ans+=up;}//cout<<ans<<endl;printf("%d\n",ans);}return 0;
}

这篇关于hdu 4803 Poor Warehouse Keeper（贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！