【算法】数学
【题解】
1.平均数：累加前缀和。//听说要向下取整？
2.中位数：双堆法，大于中位数存入小顶堆，小于中位数存入大顶堆，保证小顶堆内数字数量≥大顶堆，奇数则取小堆顶，偶数则取两堆顶/2。
3.方差=(平方的均值)-(均值的平方)，即对于a,b,c，s2=(a2+b2+c2)/3-((a+b+c)/3)2。
#include<stdio.h> #include<algorithm> #include<cstring> #include<set> #include<cctype> using namespace std; const int maxn=1000010; multiset<int>q2;//小顶堆 struct cmp { bool operator() (const int a,const int b)const {return a>b;} }; multiset<int,cmp>q1;//大顶堆 int n,k,a[maxn],sum[maxn],tot1,tot2; long long sums[maxn]; double ans2; int read() { char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } void compair() { if(tot1>tot2) { int now=*q1.begin();tot1--;//????????? q1.erase(q1.begin());//一定要删除指定位置，删除multiset中的键值会把全部键值等于的都删掉。 q2.insert(now);tot2++; } if(tot2-1>tot1) { int now=*q2.begin();tot2--; q2.erase(q2.begin()); q1.insert(now);tot1++; } if((tot1+tot2)%2) ans2=*q2.begin(); else ans2=1.0*(*q1.begin()+*q2.begin())/2; } int main() { n=read(),k=read(); sum[0]=0;sums[0]=0; int tot=0,task=0; for(int i=1;i<=n;i++) { task=read(); if(task==1) { tot++; a[tot]=read(); if(tot>k) {if(a[tot-k]<ans2)q1.erase(q1.find(a[tot-k])),tot1--;else q2.erase(q2.find(a[tot-k])),tot2--;} sum[tot]=sum[tot-1]+a[tot]; if(a[tot]>=ans2)q2.insert(a[tot]),tot2++; else q1.insert(a[tot]),tot1++; compair(); sums[tot]=sums[tot-1]+a[tot]*a[tot]; } else if(task==2) { if(tot<k)printf("%d.00 ",(sum[tot])/tot);else printf("%d.00 ",(sum[tot]-sum[tot-k])/k); } else if(task==4) { printf("%.2lf ",ans2); } else if(task==3) { if(tot<k)printf("%.2lf ",1.0*(sums[tot])/tot-1.0*(1.0*sum[tot]/tot)*(1.0*sum[tot]/tot));else//1.0进入 printf("%.2lf ",1.0*(sums[tot]-sums[tot-k])/k-1.0*(1.0*(sum[tot]-sum[tot-k])/k)*(1.0*(sum[tot]-sum[tot-k])/k)); } } return 0; }