?
题意：，Bi可以是小数。
思路：很机智的想法，对于连续M个1+N个0的一块来说，最优解一定是，Bi=M/（M+N），因为Bi是递增的（可以手推），所以如果出现在后面的一块中的Bi>前面一块的Bi，那么就不可能取到最优解，所以将两块合并一起处理，这样过程中就需要用栈来维护了。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 105 #define INF 0x7fffffff #define eps 1e-8 typedef long long LL; typedef unsigned long long ULL; using namespace std; int aa[1000005]; struct Line { int t0,t1; double val; void calc() { val=(double)t1/(double)(t1+t0); } double sum() { return val*val*(double)(t0)+(1-val)*(1-val)*(double)(t1); } } l[1000005],h; int main() { int T; scanf(%d,&T); while(T--) { memset(l,0,sizeof(l)); memset(aa,0,sizeof(aa)); int tot,head=-1,tail=-1; scanf(%d,&tot); for(int i=0; i =0; i--) if(aa[i]==0) { tail=i; break; } if(tail<=head) printf(0.000000 ); else { int t=head,top=0; while(t st; while(!st.empty()) st.pop(); for(int i=0;i l[i].val) { h=st.top(); st.pop(); l[i].t0+=h.t0; l[i].t1+=h.t1; l[i].calc(); } st.push(l[i]); } } double ans=0; while(!st.empty()) { h=st.top(); ans+=h.sum(); st.pop(); } printf(%.6lf ,ans); } } return 0; }
，Bi可以是小数。