好吧我承认我有点懒。。。。程序跑到一半Wa了,然后我找不到哪里错了。。。但是大体思路是没错的。
最开始是推出来11100这样的数据化为一组,他们的b是一样的,但是后来不知道怎么处理他们了。。。。
再看题解,说是每个区间求平均数作为b,若后面那个区间的平均数比前面那个区间小,就两个区间合并,在求平均值。不知道为什么。很苦恼啊。
先凑合着看看。
#include <stdio.h> #define maxn 100010 #define inf 2e9 int n,a[maxn]; int situ[maxn][2]; double x[maxn],sum; int p; void init() { int i,j,k; int flag=0; p=0; a[0]=0;a[n+1]=1; for(i=1,j=0,k=0;i<=n;i++) { if(a[1]==0) flag=1; if(flag&&a[i]) flag=0; if(!flag) { if(!a[i-1]&&a[i]) { if(p) { situ[p][0]=i-k; situ[p][1]=k-j;//printf("**%d %d\n",i-k,k-j); } j=i; p++; } if(a[i-1]&&!a[i]) k=i; if(i==n&&!a[n]) { i=i+1; situ[p][0]=i-k; situ[p][1]=k-j; // printf("**%d %d\n",i-k,k-j); p++; } } } } double mathe(double x,int b,int a) { double y; y=(a+b)*x*x-2*a*x+a; //printf("%6lf %d %d %6lf\n",x,b,a,y); return y; } void find() { init(); int i,j,k; j=1; x[0]=-inf; for(i=1;i<p;i++,j++) { x[j]=(double)situ[i][1]/(situ[i][0]+situ[i][1]); if(x[j]<x[j-1]) { double temp=(double)(situ[i-1][1]+situ[i][1])/(situ[i-1][1]+situ[i-1][0]+situ[i][0]+situ[i][1]); x[j]=x[j-1]=temp; } } for(i=1;i<p;i++) sum+=mathe(x[i],situ[i][0],situ[i][1]); } int main() { int t; scanf("%d",&t); while(t--) { sum=0; scanf("%d",&n); int i,j; for(i=1;i<=n;i++) scanf("%d",&a[i]); find(); printf("%.6lf\n",sum); } }