二分答案做法再次不作赘述,在此讲一种$O(n)$的做法
先处理出原数组的前缀和,然后可以发现,平均数$\frac{S_r-S_{l-1}}{r-(l-1)}$其实是前缀和函数图像割线的斜率。
维护一个前缀和函数$(x,S_x)$的上凸包,延迟为f地插入每个点。
将队尾出列的条件为$slope(q_{tail},i-f)\leq slope(q_{tail-1},i-f)$ 即维护凸包
将队首出队的条件为$slope(q_{head},i)\leq slope(q_{head+1},i)$ 维护队首最优决策,如果现在用不到以后一定用不到,不会产生更优的答案,因为$q_{head+1}$明显更优秀。
不会的小伙伴可以在纸上画个凸包推一推。
code:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+20;
int f,n,h,t,q[N],a[N];
int X(int x)
{return x;}
int Y(int x)
{return a[x];}
#define lb long double
lb slope(int a,int b)
{return (1.0*Y(a)-Y(b))/(1.0*X(a)-X(b));}
signed main()
{
cin>>n;
cin>>f;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=1;i<=n;++i)
a[i]+=a[i-1];
int head = 1 , tail = 0;
lb ans = 0 ;
//队列中存的是转移左端点-1
for(int i=f;i<=n;++i)
{
int ys = i-f ; //延迟f个点插入
while(head<tail&&slope(q[tail],ys)<=slope(q[tail-1],ys)) tail--;
q[++tail]=ys;
while(head<tail&&slope(q[head],i)<=slope(q[head+1],i)) head++;
ans = max(ans , slope(q[head],i));
}
printf("%d\n",(int) floor(1000*ans));
}
稍微指正一下,实际上维护的是 $(x, S_x)$ 的下凸壳,这样才能保证队列从
tail
到head
两点之间的斜率是单调递增的。可以帮我看看我的为什么错误吗#include[HTML_REMOVED]
using namespace std;
long long dp[100005];
int main()
{
long long ans = 0;
vector[HTML_REMOVED] sum;
long long n, f, a;
scanf(“%lld%lld”, &n, &f);
for(int i = 0; i < n; i){
scanf(“%lld”, &a);
sum.push_back(a);
}
dp[0] = sum[0];
for(long long i = 1; i < n; i){
dp[i] = dp[i-1] + sum[i];
}
ans = dp[f-1];
for(long long i = f; i < n; i++){
ans = max(ans, dp[i] - dp[i-f]);
}
printf(“%lld”, ans * 1000 / f);
return 0;
}
为什么明显更优秀
tql,好像双指针做法
tql,%%%%%%%%%%
斜率优化被你玩明白了是吧
玩♂明白
%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%
orz%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%%%%%%%
%%%%
牛n……
%%%%%%%
%%%