题解：CF830C Bamboo Partition

· · 题解

duel 场切 *2300 祭。

首先推式子，最后的结果与 此处 相同（即 \displaystyle nd-\sum a+d \sum^n_{i=1} \lfloor\frac{a_i-1}{d}\rfloor），所以过程略。

下面令 f(x)=nx-\sum a+x \sum\limits^n_{i=1} \lfloor\frac{a_i-1}{x}\rfloor。

然后由于这个形式很能整除分块，由于一个块内的 \sum\lfloor \frac{a_i-1}{d}\rfloor 相同，所以 f(x) 满足单调性。因此二分最大的 x 满足 f(x) \le k 即可。

设 R=k+\sum a。

时间复杂度 O(n\sqrt{R}\log R)。

然后 duel 的时候脑子爆炸了想不到二分，然后直接取右端点就过了，证明待补。

时间复杂度就直接优化到 O(n\sqrt{R}) 了。

这里是直接取右端点的代码。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[105];
signed main(){
    int n,k,S=0,ans=0;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],S+=a[i];
    int R=S+k;
    for(int l=1,r;l<=R;l=r+1){
        r=R/(R/l);
        int sum=n*r-S;
        for(int i=1;i<=n;i++) sum+=(a[i]-1)/r*r;
        if(sum<=k) ans=r;
    }
    cout<<ans;
}

二分就没有代码了，可以根据上面的代码自己写一份就当是作业。