【贪心】hdu4803 Poor Warehouse Keeper

题意：一开始有1个物品，总价是1。你的一次操作可以要么使得物品数量+1，总价加上当前物品的单价。要么可以使得总价+1，物品数量不变。问你最少要几次操作从初始状态到达有x个物品，总价是y的状态。这里的y可以有小数点后的部分，会抹去。

如果x>y，显然无解。

因为不管怎样操作，物品的单价是单调不下降的。所以一个naive的贪心策略是先用第二种操作，将物品提升到最大的可能单价(<(y+1)/x)，然后再用第一种操作操作到不能再操作为止，剩余的部分用第二种补齐。然而这是不对的。

我们发现，第一种操作，使得单价不改变，但是会使得第二种操作下，单价上升的斜率降低了，于是，我们每次先用第二种操作尽力将物品提升到当前最大的可能单价，然后用一下第一种操作，这时没准就能再用用第二种操作提升单价了，使得后续操作效率提高。由于x<=10，所以可以暴力模拟。

剩余的零散操作补齐即可。

#include<cstdio>

#include<algorithm>

#include<cmath>

const double eps=0.0000001;

using namespace std;

int x,y;

int main(){

    while(scanf("%d%d",&x,&y)!=EOF){

        if(x>y){

            puts("-1");

            continue;

        }

        int xnow=1,ans=0;

        double ynow=1.0;

        while(xnow<x){

            double t=(double)(y+1)*(double)xnow/(double)x;

            ans+=(int)(t-eps-ynow);

            ynow+=(double)(int)(t-eps-ynow);

            ++ans;

            ynow+=ynow/(double)xnow;

            ++xnow;

        }

        printf("%d\n",ans+y-(int)(ynow+eps));

    }

    return 0;

}