[题解] CF1661F Teleporters

· · 题解

显然我们可以把 a 所分成的每段距离分开来考虑

设 f(len,x) 表示长度为 len 的区间额外放 x 个传送器的代价

显然平均分配每段距离是最优的，于是有 f(len,x)=(x-(len\bmod (x+1)))(\lfloor \frac {len}{x+1}\rfloor)^2+(len\bmod (x+1))(\lceil \frac{len}{x+1}\rceil)^2

观察一下这个式子，我们可以得到一个结论：f(len,x)-f(len,x+1) 是单调不增的（不太会证，但可以理解一下（

也就是说每一段每增加一个传送器代价减少的变化量单调不增

我们考虑二分一个最少减小量 d，对于每一段距离二分求出 f(len,x-1)-f(len,x)\ge d 的最大的一个 x，并在这一段放 x 个传送器，设这样的总代价为 g(d)，显然我们要求出 g(d)\le m 的最大的一个 d

假设这个 d 已经求出来了，但我们会发现 d 其实不一定是最优解，也就是说可以在 d+1 的基础上加若干个传送器满足总代价 \le m，而不一定要把 d 的全部加进去

我们可以先把 g(d+1) 算出来，由于每增加一个传送器代价必定减少 d，那么我们就可以把最少增加的传送器个数算出来了：\lceil\frac{g(d+1)-m}{d}\rceil

时间复杂度 \mathcal O(n\log^2a)

code:

#include<bits/stdc++.h>
#define int long long
#define MAXN 200010
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,a[MAXN];
int f(int len,int x){
    int cr=len%(x+1),cl=x+1-cr;
    int vr=(len+x)/(x+1),vl=len/(x+1);
    return vr*vr*cr+vl*vl*cl;
}
pii calc(int len,int del){
    int l=1,r=len-1,ret=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(f(len,mid-1)-f(len,mid)>=del)
            ret=mid,l=mid+1;
        else r=mid-1;
    }return mp(f(len,ret),ret);
}
pii check(int del){
    pii ret=mp(0,0);
    for(int i=1;i<=n;i++){
        auto now=calc(a[i],del);
        ret.fi+=now.fi;ret.se+=now.se;
    }return ret;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=n;i;i--)a[i]-=a[i-1];
    scanf("%lld",&m);
    int l=0,r=inf,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid).fi<=m)l=mid+1,ans=mid;
        else r=mid-1;
    }
    auto R=check(ans+1);
    printf("%lld",R.se+(R.fi-m+ans-1)/ans);
    return 0;
}