标签：int res Average back 斜率 front sum
- 二分答案转化为判定，这样我们就只关心最大的和是否大于0，而不关心除以区间长度的干扰了
- 赛场上阴差阳错地写对了斜率优化，但是想不明白原理，几经周折查找资料，终于明白了：
- 弹出队头决策的确会导致当前解未必最优，但一定不会干扰全局最优解；如果需要查找当前最优解，则需要二分下凸壳
- 在DP的斜率优化中，是确定了斜率，自下而上用直线扫描，求最小截距的；本题则是确定了点，求最大斜率
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[100005];
long long sum[100005];
double ans;
deque<int>q;
double k(int j,int i)
{
return 1.0*(sum[j]-sum[i])/(j-i);
}
void add(int id)
{
while(q.size()>1)
{
int i=q.back();
q.pop_back();
int j=q.back();
if(k(id,i)>k(i,j))
{
q.push_back(i);
break;
}
}
q.push_back(id);
}
void calc(int n,int x)
{
double res=0;
q.clear();
if(x==1)
{
add(0);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
while(q.size()>1)
{
int j=q.front();
q.pop_front();
int l=q.front();
if(k(i,j)>k(i,l))
{
q.push_front(j);
break;
}
}
if(!q.empty())
{
res=max(res,k(i,q.front()));
}
if(i-x+1>=0)
{
add(i-x+1);
}
}
ans+=res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,m,x,y;
cin>>n>>m>>x>>y;
calc(n,x);
calc(m,y);
cout<<fixed<<setprecision(10)<<ans<<endl;
return 0;
}
标签：int,
res,
Average,
back,
斜率,
front,
sum
From： https://www.cnblogs.com/watersail/p/18447103