数学不好,给跪了
#include<iostream> #include<cstring> #include<cstring> #include<cstdio> #include<algorithm> #include<map> #include<stack> using namespace std; int n; int a[111111]; struct node { int l,r; int s; }; stack<node>st; int main() { int t; scanf("%d",&t); while(t--) { while(!st.empty())st.pop(); scanf("%d",&n); for(int i=1; i<=n; i++)scanf("%d",&a[i]); for(int i=1; i<=n; i++) { node temp; temp.l=i; temp.r=i; temp.s=a[i]; while(!st.empty()) { node tt=st.top(); if(tt.s*(temp.r-temp.l+1)>temp.s*(tt.r-tt.l+1)) { temp.l=tt.l; temp.s+=tt.s; st.pop(); } else break; } st.push(temp); } double ans=0; while(!st.empty()) { node temp=st.top(); st.pop(); double pp=(double)temp.s/(double)(temp.r-temp.l+1); double num0=temp.r-temp.l+1-temp.s; double num1=(temp.r-temp.l+1)*1.0-num0; ans+=num0*(pp*pp)+num1*(1.0-pp)*(1.0-pp); } printf("%.6f\n",ans); } return 0; }