F. Teleporters

题意

直线上有n+1个传送机，位于点0, a1, a2, a3, …, an。
如果在点x和点y都有传送机，那么可以花费(x − y) ^ 2点成本从点x传送到点y。
我们可以在整数点上安装一些额外的传送机，这样就可以使得成本在不超过m的情况下，从点0到点an。
求出安装额外传送机的最小数目。

输入

第一行包含一个整数n (1 ≤ N ≤ 2*10^5 )

第二行包含n个整数a1，a2，…，an（1≤ a1< a2< a3< ⋯< an≤10^9)

第三行包含一个整数m (an ≤ m ≤ 10^18)

输出

一个整数，表示安装额外传送带的最小值。

思路

• 题目中要求我们求最小值，我们发现大于这个最小值一定满足成本不超过m，而小于
  最小值成本一定会超过m。那么我们想到这个条件，一定可以使用二分来查找最小值。
  那么接下来就是在O(n)的复杂度内判断安装k个额外传送带成本是否不超过m

• 由于题目中存在现有的传送带，而且这些传送带我们无法改变其位置，那么我们就
  可以把题目所给的n+1固定传送带看做划分成了n部分，每部分的长度
  是V[i]-V[i-1] (当前位置减去前一个的位置)

• 紧接着我们便是考虑有k个额外传送带的情况下如何分配给这个n个部分，使得成本最小。
  我们先考虑一个部分的情况。假设这个部分长度为res，给了k个额外传送带。由题目中
  的成本为(x - y) ^2，我们想到这个不等式 x^2 + y^2 >= (x + y) ^ 2 即将长度为res
  平均分为k段会使得成本最低。由于数据为整数，即为分为k段长res/k和res/k+1时会使
  成本最小。即得到公式:成本 = (res/k)^2 * k + (res%k) * (2 * res/k + 1)

• 接下来我们发现现在虽然知道一个长为res的部分分配k个时成本最低，但是
  我们仍然无法解决有n个部分时k个如何求得最小值。这时我们再看成本(x - y) ^ 2
  如果数据不是整数时，一个部分的公式是什么呢？ 是(res^2) / k。那么我们再给这个
  部分分配一个，让它可用的数量变为k+1个时，成本变为了(res^2) / (k+1)。换个角度想
  我们这个额外的传输带使成本降低了(res^2) / (k * (k + 1))。我们考虑这个函数的积分
  那么他的导函数就是(res/k)^2。令(res1/k1)^2 = (res2/k2)^2 ,我们发现k1/k2 = res1/res2
  时成立。那么我们对于n个长度为res1，res2，…，resn的部分，分配k1 : k2 : k3 … =
  res1 : res2 : res3 … 时是不是最大呢？

• 到这我们便可以知道n个部分怎么分配了。就是按照res1 ：res2 ：res3 … 的比例分配
  但是我们要求的是整数，那么我们便可以考虑k1，k2，k3…kn 应该在这个数字上下波动
  但具体是多少还要程序跑一下才知道。这里我尝试到上下为小于2的时候就ac了。
  (可喜可贺 (^▽^) 这道题cf上给了7s的运行时间 俺还以为要调好几次 )

时间复杂度 O(nlogn)

本人菜鸡一枚，分享一下自己想出来的思路，还请各位大佬多多指教多多包涵 (^o^)/~

附上ac代码

#include<iostream>
#include<map>
using namespace std;
typedef pair<long long,long long> pii;
const int num=2e5+10;

multimap<long long,pii> inx;
multimap<long long,pii>::iterator it;
long long inv[num];
long long date_sum;
long long n,m;

long long check(long long n1,long long x1){
    if(x1==0)return 1e10;
    if(x1>=n1)return n1;
    long long z1=n1/x1;
    long long sum1=n1+2*n1*z1-z1*z1*x1-z1*x1;
    return sum1;
}

long long check_tool(long long p){
    inx.clear();
    long long date_tool_sum=0,date_tool=0;
    for(int i=1;i<=n;i++){
     long long a=p*inv[i]/date_sum;
     long long res1,res2;
     if(a>0){
        res1=check(inv[i],a);
        res2=check(inv[i],a+1); 
     date_tool+=a-1;
     date_tool_sum+=res1;
     inx.insert({res2-res1,{inv[i],a+1}});
     }else{
        res1=check(inv[i],a+1);
        res2=check(inv[i],a+2); 
     date_tool+=a;
     date_tool_sum+=res1;
     inx.insert({res2-res1,{inv[i],a+2}});

     }
    }

    date_tool=p-date_tool;
    for(int i=1;i<=date_tool;i++){
        it=inx.begin();
        date_tool_sum+=it->first; 
        long long res1=check(it->second.first,it->second.second);
        long long res2=check(it->second.first,it->second.second+1);
        inx.insert({res2-res1,{it->second.first,it->second.second+1}});
        inx.erase(it);
    }
    return date_tool_sum;
}

long long get_tool(long long start,long long end){
    if(start==end)return start;
    if(end-start==1){
        if(check_tool(start)<=m)return start;else return end;
    }
    int mid=(start+end)/2;
    if(check_tool(mid)<=m)return get_tool(start,mid);else return get_tool(mid+1,end);
}

int main(){ 
    cin>>n;
    for(int i=1;i<=n;i++)cin>>inv[i];
    cin>>m; 
    date_sum=inv[n];
    for(int i=n;i>=1;i--){
        inv[i]=inv[i]-inv[i-1];
    }
    cout<<get_tool(0,date_sum)<<endl;

}