codeforces Gym - 101485 D Debugging (2015-2016 Northwestern European Regional Contest (NWERC 2015))

题目描述：

点击打开链接

这题题意其实很不好理解，你有一个n行的程序，现在程序运行了r时间之后停止了运行，证明此处有一个bug，现在你需要在程序中加printf来调试找到bug所在的位置，你每次加一个printf所需的时间为p，为你在最坏的情况下最少需要多少时间找到bug。

枚举二分三分四分一直到n-1

查询一般二分查找，这个因为有个printf条件可以实现精准3分到n-1分查找，

因为三分的话也可以像二分一样确定到底是哪个

就像1000范围内猜数如果三分能确定的话就不会用二分但是三分并不能确定

因为你猜数他只告诉你你报的（一个）数与答案大小的比较

而这个printf可以告诉你2个三个或者更多所以可以三分四分等等

几分最优是由n的大小和printf辅助时间二者共同确定的

二分是log2N+printf的时间*log2N 的样子然后三分是log3N+printf的时间*log3N

所以枚举几分的同时也要记录 n为某个值时的最优时间下次再到这个值时就不用重复搜索了

#include <bits/stdc++.h>

#include <cmath>

using namespace std;

#define ll long long

#define F(i,a,b) for(ll i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

ll n;

ll r,p;

ll a[];

ll dfs(ll n)

{

    ll ans=1e18;

    if(n==||n==) return ;

    if(a[n]) return a[n];

    F(i,,n-)

    {

        ans=min(ans,dfs(n/(i+)+((n%(i+))?:))+i*p+r);

    }

    return a[n]=ans;

}

int main()

{

    cin>>n>>r>>p;

    ll ans=;

    if(n==) { puts("");return ; }

    ans=dfs(n);

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

    return ;

}

巴特西

codeforces Gym - 101485 D Debugging (2015-2016 Northwestern European Regional Contest (NWERC 2015))

最新文章

热门文章