【题解】伐木工

题意

有根长度为的木头，表示对长度为的木头进行每米切割一次，例如木头会被切割成三段。现在进行的操作。操作完之后剩下有段木头，求原来的是多少。

题解

题面的中转换一下就可以变为，先解决第一个问题，这个求和如何快速求解，由于是取整操作，对于不同的值其取整的值可能是一样的，而且不同数的级别的的，因为一个数是由构成的，所以不同的数只会有级别个。所以在某个区间内的值是一样的。那么已知该区间的左端点为，如何求解右端点呢。由于的值是单调递减的，所以可以考虑用二分来查找右端点。

int Find(int n,int i)
{
    int x=(n+i-1)/i;
    int l=i;
    int r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if((n+mid-1)/mid<x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r;
}

这样就能在的复杂度下来求解的值了。然后再考虑已知的值如何求解。由于该求和函数也是具有单调性的，所以我们可以使用二分来求解，每次的带入我们上面说到的求解方法求出其值，若其值大于说明右区间大了，反之左区间小了。若等于则退出。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
int Find(int n,int i)
{
    int x=(n+i-1)/i;
    int l=i;
    int r=n;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if((n+mid-1)/mid<x)
            r=mid-1;
        else
            l=mid+1;
    }
    return r;
}
long long f(int n)
{
    long long ans=0;
    for(int i=1,last; i<=n; i=last+1)
    {
        last=Find(n,i);
        ans+=(last-i+1)*((n+i-1)/i);
    }
    return ans;
}
int main()
{
    long long m;
    scanf("%lld",&m);
    int flag=0;
    int l=1;
    int r=1e9;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        long long fmid=f(mid);
        if(fmid==m)
        {
            printf("%d\n",mid);
            flag=1;
            break;
        }
        if(fmid<m)
            l=mid+1;
        else
            r=mid-1;
    }
    if(!flag)
        printf("-1\n");
    return 0;
}