Codeforces 985D

题意略。

思路：这个题本来打算先推一下公式，然后解方程来算。函数图像大概如下：

最左端为H。但是由于中间那个尖的地方（假设它的高度为h），可能在那个地方有多堆沙包，所以推公式貌似不行。

但是最高高度h和面积之间是存在函数关系的，所有堆沙堡的方式应该都是类似于这样的。所以我们想找出一个方式，使得所用沙包数为n，

且占地最少。也是就说我们要找出最高的且合法的h，并算出它的占地。

详见代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

LL n,H;

LL cal(LL h){

    LL ret = ;

    ret += h * (h + ) / ;

    if(h > H){

        ret += (H + h - ) * (h - H) / ;

    }

    return ret;

}

int main(){

    scanf("%lld%lld",&n,&H);

    LL lft = ,rht = ;

    LL ans = n;

    while(lft < rht){

        LL mid = (lft + rht + )>>;

        LL area = cal(mid);

        if(area <= n){

            lft = mid;

            LL temp = mid;

            if(mid >= H)

                temp += (mid - H);

            LL last = (n - area);

            temp += last / mid + (last % mid > );

            ans = min(ans,temp);

        }

        else{

            rht = mid - ;

        }

    }

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

    return ;

}

这里要注意一下，二分的右端值rht，由于在最差情况下，h * (h + 1) / 2 = 1e18，也就是说，hmax = sqrt(2 * 1e18)，因此设置为1.5 * 1e9。

巴特西

Codeforces 985D

最新文章

热门文章