斜率优化鼻祖题
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,f;
int sum[maxn];
int q[maxn],h,t;
double K(int i,int j)
{
return double(sum[j]-sum[i])/double(j-i);
}
int main(int argc, char const *argv[])
{
scanf("%d%d",&n,&f);
for(int i = 1,x; i <= n; ++i)
scanf("%d",&x),sum[i]=sum[i-1]+x;
double ans = 0;
h = 1; t = 0;
for(int i = f; i <= n; ++i)
{
while(h<t&&K(q[h],i)<K(q[h+1],i))h++;
ans=max(ans,K(q[h],i));
int k = i-f+1;
while(h<t&&K(q[t-1],q[t])>K(q[t],k))t--;
q[++t]=k;
}
printf("%d",(int)(ans*1000));
return 0;
}