Educational Codeforces Round 126 (Rated for Div. 2) F.Teleporters

题目

数轴的正轴上有n(n<=2e5)个整点，

从点i到j的代价是二者距离差的平方，给定一个

你需要从0到，代价不超过=a_{n})" src="https://latex.codecogs.com/gif.latex?m%28m%3E%3Da_%7Bn%7D%29" />，问最少加多少个整点，时限7秒

思路来源

梁神

题解

想正解之前不妨考虑朴素怎么做，然后再考虑怎么优化，dp如此，线段树&&二分亦然

n个初始整点有n段线段长度距离，考虑给第i段上面加a个点，和给第i段上面加a+1个点，

二者相比，加了一个点，有一个对应代价减少的值，记为x，

如果能暴力维护优先队列，显然是每次找x最大的值，

把a取出来，总代价减去x，再把a+1丢回去，

那就可以考虑二分这个过程，二分所有的线段，增量代价减少的值>x的都被用完了的最小x，

求出这个x之后，再对每条线段二分实际插入了多少个点L，才使得加L个点减去加L+1个点的增量不超过x，通过L计算对代价总和的贡献

等于x的增量可能用了一部分，这里是先考虑把x的增量都用了，

此时必小于m，因此可以考虑回退delta/x个点，

由于是x的出现使得从>m变成<=m，所以x一定够用，直接除

心得

思路不复杂，但调了好久的大于号和大于等于号，导致E题口嗨完没时间写了

梁神：你真的会写二分查找吗？我：显然不会。

代码

#include
using namespace std;
const int INF=0x3f3f3f3f,N=2e5+10;
#define dbg1(x) cerr<<(#x)<<" "<<(x)<<" ";
#define dbg2(x) cerr<<(#x)<<" "<<(x)<<" "<x)return x;
    ll v=x%a,r=x/a;
    ll ans=v*sq(r+1)+(a-v)*sq(r);
    return ans;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=a[i]-a[i-1];
    }
    scanf("%lld",&m);
    ll l=0,r=mx;
    while(l<=r){
        ll mid=(l+r)/2,sum=0;
        for(int i=1;i<=n;++i){
            ll L=1,R=b[i];
            while(L<=R){
                ll M=(L+R)/2;
                if(cal(b[i],M)-cal(b[i],M+1)>=mid){
                    L=M+1;
                }
                else{
                    R=M-1;
                }
            }
            sum+=cal(b[i],L);
        }
        if(sum<=m){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    for(int i=1;i<=n;++i){
        ll L=1,R=b[i];
        while(L<=R){
            ll M=(L+R)/2;
            if(cal(b[i],M)-cal(b[i],M+1)>=r){
                L=M+1;
            }
            else{
                R=M-1;
            }
        }
        sum1+=cal(b[i],L);
        tot1+=L-1;
    }
    printf("%lld\n",tot1-(m-sum1)/r);
    return 0;
}