F. Teleporters

Problem - F - Codeforces

给你一个x正方向数轴，N个点，每两个点cost为，问若使0到cost不大于m，你要添加的最小点的数量。

首先预处理每两个点的距离差，我们要使cost不大于m，就要让cost最大的那几个区间插几个数进去对吧。那么直观的想是不是可以搞个优先队列把区间的cost都丢进去，每次取队头出来分几段再丢进去。但是分几段呢？不知道。

那么换个思路：答案具有二分性质，那么考虑去降低cost，二分出使cost不大于m的最小降低值，再遍历一遍，对每个区间二分出需要的插入个数，看看最后有没有剩（因为二分是所有都满足，但不一定是最优解），再减去剩的就能解出答案了。

看起来十分可行。二分cost很简单，判断cost和m的大小即可。但是怎么二分这个区间要插入的个数呢？

首先，插入越多，降低越多；但是越插入到后面， 每次降低的值也越少，所以降低值也是单调的。

那么我们在二分是写一个计算calculate，算出当前区间长度和插入个数所含的cost。

此时把当前插入个数mid和当前插入个数mid+1的cost做差，就能得到这次降低的值。这是单调递减的。

假如这个值比二分的降低值大，则说明还需要更多的插入，l=mid+1；假如说这个值比它小，则可以少插入几个，r=mid-1（加加减减比较抽象）。一直找到差小于二分的cost点，这个过程和最开始口胡的把最大的那几个区间丢进去的过程相似（也解决了前面的疑问：到底分几段？不知道。看你要多少，就分多少，都是单调的就都能二分去找）。最后相当于降mid次，即插mid个点。

我们二分出这个值小于cost的最大值，再在遍历时把每个区间插入后用cal计算并加起来，得到在降低当前值下的cost，和m比较则得到了不大于m的最大降低值。

最后需要减去剩的。

/*keep on going and never give up*/
#include
using namespace std;
#define int long long
#define endl "\n" 
#define pb push_back
#define dbg1(x) cerr<<(#x)<<" "<<(x)<<" ";
#define dbg2(x) cerr<<(#x)<<" "<<(x)<<" "<x)return x;
    int v=x%a,r=x/a;
    int ans=v*sq(r+1)+(a-v)*sq(r);
    return ans;
}//算区间cost，建议手推。
signed main(){
	fast cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    cin>>m;
    int l=0,r=mx;
    while(l<=r){//二分cost
        int mid=(l+r)/2,sum=0;
        for(int i=1;i<=n;++i){
            int L=1,R=b[i];
            while(L<=R){//二分个数
                int 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){//判断每个区间具体几个，减去多余的，因为之前的二分值是满足所有的，现在细分到每个区间，肯定有剩余（大概。
        int L=1,R=b[i];
        while(L<=R){
            int 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;
    }
    cout<