2020 BIT冬训-二分三分快速幂矩阵 D - Sand Fortress CodeForces - 985D

Problem Description

You are going to the beach with the idea to build the greatest sand castle ever in your head! The beach is not as three-dimensional as you could have imagined, it can be decribed as a line of spots to pile up sand pillars. Spots are numbered 1 through infinity from left to right.

Obviously, there is not enough sand on the beach, so you brought n packs of sand with you. Let height h_i of the sand pillar on some spot i be the number of sand packs you spent on it. You can‘t split a sand pack to multiple pillars, all the sand from it should go to a single one. There is a fence of height equal to the height of pillar with H sand packs to the left of the first spot and you should prevent sand from going over it.

Finally you ended up with the following conditions to building the castle:

• h₁?≤?H: no sand from the leftmost spot should go over the fence;
• For any  |h_i?-?h_i?+?1|?≤?1: large difference in heights of two neighboring pillars can lead sand to fall down from the higher one to the lower, you really don‘t want this to happen;
• : you want to spend all the sand you brought with you.

As you have infinite spots to build, it is always possible to come up with some valid castle structure. Though you want the castle to be as compact as possible.

Your task is to calculate the minimum number of spots you can occupy so that all the aforementioned conditions hold.

Input

The only line contains two integer numbers n and H (1?≤?n,?H?≤?10¹⁸) — the number of sand packs you have and the height of the fence, respectively.

Output

Print the minimum number of spots you can occupy so the all the castle building conditions hold.

Examples

5 2

3

6 8

3

Note

Here are the heights of some valid castles:

• n?=?5,?H?=?2,?[2,?2,?1,?0,?...],?[2,?1,?1,?1,?0,?...],?[1,?0,?1,?2,?1,?0,?...]
• n?=?6,?H?=?8,?[3,?2,?1,?0,?...],?[2,?2,?1,?1,?0,?...],?[0,?1,?0,?1,?2,?1,?1,?0...] (this one has 5 spots occupied)

The first list for both cases is the optimal answer, 3 spots are occupied in them.

And here are some invalid ones:

• n?=?5,?H?=?2,?[3,?2,?0,?...],?[2,?3,?0,?...],?[1,?0,?2,?2,?...]
• n?=?6,?H?=?8,?[2,?2,?2,?0,?...],?[6,?0,?...],?[1,?4,?1,?0...],?[2,?2,?1,?0,?...]

注意这题是最左边的高度不能大于H。（一开始以为是最大高度不能大于H，一直wa）

二分法寻找答案。需要用到等差数列公式和根据题目得出的等式。

若mid<=h。那么就以高度1,2,3,…，mid为他的最大值即mid*(mid+1)/2。

若mid>h。那么令最左边的为h。最高的高度为hig。

从最左边依次过去是h,h+1,…,hig-1,hig,(hig),hig-1,…，2,1。

我们可以发现，当mid-h为奇数时，最高高度出现2次，为偶数时则只出现一次。

我们可以通过计算得出hig=h+(mid-h)/2。

再根据上述就可以得出mid所能占据最大的值cnt。

查找到最小的那个大于n的cnt所对应的mid即是答案。

AC代码如下（这题洛谷上的难度标注是提高+/省选-，tql）：

#include<cstdio>
#include<algorithm>
using namespace std;
long long n,h,l,r,cnt,ans,mid,flag,hig;
int main(){
    scanf("%lld%lld",&n,&h);
    l=1,r=n;
    while(r>l){
        mid=(l+r)/2;
        ans=0;
        flag=0;
        if(mid<=h){
            if(mid>2e9)
                flag=1;
            else
                ans=mid*(mid+1);
        }else{
            hig=h+(mid-h)/2;
            if(hig>2e9)
                flag=1;    
            else{
                if((mid-h)&1)
                    ans=(hig+h)*(hig+1-h)+hig*(hig+1);
                else
                    ans=(hig+h-1)*(hig-h)+hig*(hig+1);
            }
        }
        if(ans==2*n){
            r=mid;
            break;
        }else if(ans>(2*n)||flag){
            r=mid;
        }else
            l=mid+1;
    }
    printf("%lld\n",r);
}

2020 BIT冬训-二分三分快速幂矩阵 D - Sand Fortress CodeForces - 985D

原文：https://www.cnblogs.com/mikku39/p/14402563.html