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*/#includeusing 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>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=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)  L=M+1;     else R=M-1; } sum1+=cal(b[i],L); tot1+=L-1;    }    cout<<tot1-(m-sum1)/r;//再试探性看看有没有剩。    return 0^0;}

PS：

xswl，二分都不会。2600的题惹不起。

教练说的有的coder一辈子都写不对二分诚不我欺.