數(shù)據(jù)流中的算法

?

思路：

　　線段樹模擬；

　　時間剛剛卡在邊界上，有時超時一個點(diǎn)，有時能過；

?

來，上代碼：

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define maxn 1000005int n,size,cnt,ai[maxn],L[maxn<<2],R[maxn<<2]; int mid[maxn<<2],dis[maxn<<2],to,x;double sum[maxn<<2],sum2[maxn<<2];inline void in(int &now) {char Cget=getchar();now=0;while(Cget>'9'||Cget<'0') Cget=getchar();while(Cget>='0'&&Cget<='9'){now=now*10+Cget-'0';Cget=getchar();} }void tree_build(int now,int l,int r) {L[now]=l,R[now]=r;if(l==r) return ;mid[now]=l+r>>1;tree_build(now<<1,l,mid[now]);tree_build(now<<1|1,mid[now]+1,r); }void tree_add() {int now=1,dis1=to*x,ss=to*dis1;while(L[now]!=R[now]){dis[now]+=x,sum[now]+=dis1,sum2[now]+=ss;if(to<=mid[now]) now=now<<1;else now=now<<1|1;}dis[now]+=x,sum[now]+=dis1,sum2[now]+=ss; }int tree_query(int k) {int now=1;while(L[now]!=R[now]){if(k<=dis[now<<1]) now=now<<1;else k-=dis[now<<1],now=now<<1|1;}return L[now]; }inline void out(int X) {if(X>9) out(X/10);putchar(X%10+48); }int main() {int now=0;in(n),in(size);int ty;tree_build(1,0,100);while(n--){in(ty);if(ty==1){in(ai[++now]);to=ai[now],x=1,tree_add();if(now>size) x=-1,to=ai[now-size],tree_add();continue;}if(ty==2){double res=sum[1]/(double)dis[1];out((int)res),putchar('.'),putchar('0'),putchar('0'),putchar('\n');continue;}if(ty==3){double p=sum[1]/(double)dis[1];double res=(sum2[1]-sum[1]*2*p+p*p*dis[1])/dis[1];printf("%.2lf",res),putchar('\n');continue;}if(ty==4){int p=dis[1];if(p&1) out(tree_query((p>>1)+1)),putchar('.'),putchar('0'),putchar('0'),putchar('\n');else printf("%.2f",(double)(tree_query(p>>1)+tree_query((p>>1)+1))/2.0),putchar('\n');}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6757009.html

總結(jié)

以上是生活随笔為你收集整理的AC日记——数据流中的算法 51nod 1785的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。