题解：P8424 [JOI Open 2022] 跷跷板（Seesaw）
Union_of_Britain
·
·
题解
设初始重心为 $P$，对于一个答案 $[l, r]$，设 $L_1=P-l$,则 $r$ 大致是关于 $L_1$ 增加而减小的，但是答案 $L_1+r-P$ 却被发现不具有凸性或单峰等性质。
但是一个 $L_1$ 代表 $r^{\prime}<r$ 均（可以被认为）合法。这意味着，$\left\{L_1, r\right\}$ 应该成阶梯状。根据 Quickhull 的思想，只需要把阶梯处的凹位置全都遍历一边就可以了。这可以通过二分找下一个 $r$ 不同的位置来实现。设有 $K$ 个凹点，那么时间复杂度是 $O(n K \log n)$。随机数据下，$n=2 \times 10^5$ 大概 $K=70$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define db double
const int maxn=2e5+5;
int n;
db a[maxn],P,s[maxn],ans=0;
inline db Calc(db L1){
int l=1,r=n;
db mx=P;
while(r-l>0){
while(r-l+1>1&&(s[r-1]-s[l-1])>(P-L1)*(r-l))--r;
if(r-l+1==1)break;
l++;
mx=max(mx,(s[r]-s[l-1])/(r-l+1));
}
return mx-P;
}
priority_queue<pair<db,db> > Q;
signed main(){
// freopen("balance.in","r",stdin);
// freopen("balance.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],P+=a[i],s[i]=s[i-1]+a[i];
if(n==2){
printf("%.10lf\n",(a[2]-a[1])/2.0);
return 0;
}
P/=n;
db cur=0,curc=Calc(0),ans=curc;
int cnt=0;
while(1){
++cnt;
db L=cur,R=1e9,res=-1,cres;
while(Q.size()&&(fabs(curc-Q.top().second)<1e-6||(-Q.top().first)<=cur))Q.pop();
if(Q.size())R=-Q.top().first;
while(R-L>max(L,1.0)*1e-9){
db mid=(L+R)/2.0,r=Calc(mid);
if(R-L>1e-3)Q.push({-mid,r});
if(fabs(r-curc)>1e-6)res=mid,R=mid,cres=r;
else L=mid;
}
if(res!=-1)ans=min(ans,cres+res),cur=res,curc=cres;
else break;
}
// cout<<cnt<<endl;
printf("%.10lf\n",ans);
return 0;
}```