7. 18 test 砍树题解

（题面保密，内部人员可览）

　　首先观察题面，可得出如下公式

　　　　　　∑(ceil(a[i] /d)*d−a[i])≤k

　　其中，ceil(a[i] /d)表示在需要被砍伐之前所经过的轮数，ceil函数是为了保证一定可以被砍伐，即轮数=(a[i]%d)?(a[i]/d):(a[i]/d+1)

　轮数*d表示一共生长的长度，减去a[i]即为需要砍伐的长度，取sigma即为一共需砍伐的长度，与长度上限k比较，若小于等于k，即为符合条件。

　　推得公式后，大部分OIER的思路都是二分求解，但这个题不满足二分单调性，可以手动模拟一下，有如下几种方法：

　　　　1.暴力对拍

　　　　2.将check函数返回值输出，理想状态：“1 1 1 1 1 1 1 1 0 0 0 0 0 0”，实际状态：“1 0 1 1 0 1 0 0 1 1 0”（疯狂跳跃）。。

　　　　3.将二分左端点值赋作以求得的ans值，右端点不变，再次二分，发现ans值发生变化

　　于是对于此题而言，我们应该用什么方法求解呢？

　　首先我们化简公式

　　　　　　∑(ceil(a[i] /d))≤(k+∑(a[i]))/d

　　我们不难发现 k+∑(a[i]) 是一个定值，我们设之为limit

　　考虑函数单调性思想，我们发现右侧(k+∑(a[i]))/d的值应向下取整，因为若一个函数的最大值小于另一个函数的最小值，那么这个函数小于另一个函数恒成立，由此可得解

　　那么总结规律，随着d的不断增加(k+∑(a[i]))/d的值呈分段下降，而∑(ceil(a[i] /d))也同样分段下降，且区间长度远小于前者

　　于是不难看出，可以采用数论分块向下取整的思想来处理。

　　例如：floor（107/36）=2，floor（107/53）=2，36～53即为一段区间，那么如何求呢？公式如下

　　　　r=k/(k/l);

　　证明如下：

　　而这也正是此题的核心内容

　　由于题目要求求最大的值，那么我们只需要满足每一个区间的右端点满足条件即可，因为∑(ceil(a[i] /d))满足区间单调性，若一个区间，左端点满足条件，那么整个区间一定满足条件，若右端点不满足条件，那整体一定不满足，而一个区间的最优解，一定是右端点，因此不需考虑中间交点。

　　代码如下：

#include<bits/stdc++.h>

#define re register

#define ll long long

using namespace std;

ll n,k,limit,a[];

inline ll read(){

    re ll a=,b=;re char ch=getchar();

    while(ch<''||ch>'')

        b=(ch=='-')?-:,ch=getchar();

    while(ch>=''&&ch<='')

        a=(a<<)+(a<<)+(ch^),ch=getchar();

    return a*b;

}

signed main()

{

    n=read(),k=read();limit=k;

    for(re ll i=;i<=n;++i)

        a[i]=read(),limit+=a[i];

    for(re ll d=limit;d>=;d--)

    {

        re ll flag=limit/d,tot=;

        for(re ll i=;i<=n;++i)

            tot+=(a[i]-)/d+;

        if(tot<=flag)

            {printf("%lld\n",d);return ;}

        d=(limit/(limit/d+))+;

    }

    return ;

}

巴特西

7. 18 test 砍树题解

最新文章

热门文章