HDU4803_Poor Warehouse Keeper

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目很有意思，我想说其实我在比赛的时候就看过了一下这个题目，今天才这么快搞出来吧。

其实总共按上键的次数不会超过10个，我们可以每次假设相隔按两次上键之间按了xi次下键，由于上键的次数是确定的，所以最后就是求下键的次数和最小。

同时用一个等式表达出来后我们就可以发现其实是一个sigama(xi*(n/i))=y-x+1-eps（eps是为了防止后面的数字恰等于1），求sigama(xi)的和最小。

显然，这里很简单了，由于系数是从大到小的，我们可以直接从大的开始填充，直到填充的剩余那个数在1的范围以内就可以了。

注意这里一定要考虑精度问题。。。

居然一开始用cin给T掉了，我看只有两个数输入啊，神坑啊。

#include <cstdio>

#include <cmath>

#define eps 1e-5

using namespace std;

double a[],x,y;

int ans,n;

int main()

{

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

    {

        ans=(int)(x-);

        y-=x-+eps;

        if (y<)

        {

            printf("-1\n");

            continue;

        }

        for (int i=; i<=x; i++) a[i]=x/i;

        for (int i=; i<=x; i++)

        {

            n=(int)(y/a[i]);

            ans+=n;

            y-=n*a[i];

            if (y<) break;

        }

        printf("%d\n",ans);

    }

    return ;

}