[7.18NOIP模拟测试5]砍树题解(数论分块)

冷不防 2021-10-19 20:40 380阅读 0赞

[题面(加密)][Link 1]

又考没学的姿势……不带这么玩的……

考场上打了个模拟 骗到30分滚粗了

稍加思考(滑稽)可将题面转化为：

> 求一个最大的$d$，使得
> 
> 　　$\\sum \\limits \_\{i=1\}^n \{(\\left \\lceil \\frac\{a\_i\}\{d\} \\right \\rceil \*d-a\_i)\} \\leq k$

移项可得

$\\sum \\limits \_\{i=1\}^n \{\\left \\lceil \\frac\{a\_i\}\{d\} \\right \\rceil \*d\} \\leq k+\\sum \\limits \_\{i=1\}^\{n\}\{a\_i\}$

那么$\\leq$ 右侧就变成了一个常量，我们将其设为$C$。

把$d$除过去，得到

$\\sum\_\\limits\{i=1\}^\{n\}\\lceil\\frac\{a\_i\}\{d\}\\rceil \\leq \\lfloor\\frac\{C\}\{d\}\\rfloor$

此时不等号左右都含有取整，都可以看作分段函数

我们现在想要最大的d，所以取每段的右端点一定比其它位置更优

之后求出等号左侧的$\\lceil\\frac\{a\_i\}\{d\}\\rceil$就可以通过判断更新答案

辣么怎么确定右端点呢？

这时候就需要一个东西：数论分块 ([戳这里%大佬blog][blog])

那么利用数论分块的结论：

对于形如$\\sum\_\{i=1\}^\{n\}\{\\lfloor \\frac\{n\}\{i\} \\rfloor\}$的式子，

如果一段的左端点为$l$，那么右端点为$\\lfloor \\frac\{n\}\{\\lfloor \\frac\{n\}\{l\}\\rfloor\} \\rfloor$

本题得以在$O(n \\sqrt\{a\_i\})$的优秀复杂度内解决。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const int N=105;
    int n;
    ll lim,a[N],sum,ans;
    int main()
    {
        scanf("%d%lld",&n,&lim);
        sum=lim;
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]),sum+=a[i];
        ll d=0;
        while(sum/(d+1)>0)
        {
            d=sum/(sum/(d+1));
            ll res=0;
            for(int i=1;i<=n;i++)
            {
                ll tmp=a[i]/d;
                if(a[i]%d)tmp+=1;
                res+=tmp*d;
            }
            if(res<=sum)ans=d;
        }
        cout<<ans<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Rorschach-XR/p/11208099.html

[Link 1]: https://www.cnblogs.com/Rorschach-XR/p/11207887.html
[blog]: https://www.cnblogs.com/henry-1202/p/10121854.html