poj 2018斜率DP求子序列的最大平均值

xiaoxiao2021-02-28  84

#include<cstdio> #include<cstring> #define MAX(x,y) ((x)>(y)?(x):(y)) #define MIN(x,y) ((x)>(y)?(y):(x)) struct node { double x,y; }q[100100]; double cal(double x1,double y1,double x2,double y2) { return (y1-y2)/(x1-x2); } double sum[100100]; int main() { int n,f; scanf("%d%d",&n,&f); memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { scanf("%lf",&sum[i]); sum[i]+=sum[i-1]; } q[0].x=0;q[0].y=0; int head=0,tot=0; double ans=-1; for(int i=1;i<=n;i++) { while(head<=tot&&q[head].x+f<=i) head++; if(head>0) { ans=MAX(ans,(sum[i]-q[head-1].y)/(i-q[head-1].x)); } while(head<tot&&cal(q[tot].x,q[tot].y,q[tot-1].x,q[tot-1].y)>cal(i,sum[i],q[tot].x,q[tot].y)) tot--; q[++tot].x=i; q[tot].y=sum[i]; } printf("%d\n",(int)(ans*1000)); return 0; }
转载请注明原文地址: https://www.6miu.com/read-83024.html

最新回复(0)