首页 > 代码库 > ZOJ--3612--Median【线段树+离散化】
ZOJ--3612--Median【线段树+离散化】
链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4736
题意:有最多10000次操作,在一个初始为空的数列中添加或移除元素并保持数列有序,每次操作后,如果数列个数为奇数就输出中间值,如果为偶数就输出中间两个值得平均值。
思路:刚开始写了一发multiset模拟,看吴琦TLE了估计他也是multiset写的,就放弃这个思路了,不过最后证明multiset写的机智一点这题也是能过的。线段树、树状数组都考虑了,最后还是用线段树敲了。虽然数字范围是int内,但是操作最多只有10000次,所以需要离散化。先进行离线,再进行离散化,然后建树进行操作。每个节点维护离散化后新的数组对应的下标值在数列中出现了几次。
查询的时候输入要查询数列第几个数,然后从线段树根节点开始递归判断左右子树的数字个数,如果查询的个数小于等于左子树的数字个数,则在左子树中查询,否则要查询的数字减去左子树数字的个数并在右子树中查询,如此递归直到叶子节点,返回节点值,此时返回的值是离散化数组的下标值,再输出答案就好了。
细节: 1.输出比较恶心,对于double类型不输出后导0,直接用cout是可以的,但是输出量太大可能会TLE,所以我转成字符串输出了。
2.虽然数据都在int范围内,但是相加求平均值时可能会溢出,所以用long long来存,因为这个WA了很久。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 10100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[MAXN<<2],ans[MAXN],fuck[MAXN],cha[MAXN]; int n,flag; struct node{ int num; char op; int id; }a[10100]; void pushup(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1]; } void build(int l,int r,int rt){ sum[rt] = 0; if(l==r) return ; int m = (l+r)>>1; build(lson); build(rson); } void update(int c,int x,int l,int r,int rt){ if(l==r){ if(sum[rt]==0&&x==-1){ flag = 1; return ; } sum[rt]+=x; return ; } int m = (l+r)>>1; if(c<=m) update(c,x,lson); else update(c,x,rson); pushup(rt); } int query(int c,int l,int r,int rt){ if(l==r){ return l; } //cout<<sum[rt<<1]<<" "<<l<<endl; int m = (l+r)>>1; int ret; if(sum[rt<<1]>=c){ ret = query(c,lson); } else{ ret = query(c-sum[rt<<1],rson); } return ret; } void output(double x){ int i; char ss[200]; sprintf(ss,"%lf",x); int l = strlen(ss); for(i=0;i<l;i++){ if(ss[i]=='.') break; } if(i==l){ printf("%lf\n",x); return ; } while(ss[l-1]=='0'){ l--; } if(ss[l-1]=='.') l--; for(i=0;i<l;i++){ printf("%c",ss[i]); } printf("\n"); } map<int,int>mp; int main(){ int i,j,q,t,x; char str[20]; scanf("%d",&t); while(t--){ mp.clear(); n = 0; scanf("%d",&q); for(i=1;i<=q;i++){ scanf("%s%d",str,&a[i].num); a[i].op = str[0]; a[i].id = i; fuck[i] = a[i].num; } sort(fuck+1,fuck+1+q); int p = unique(fuck+1,fuck+1+q)-fuck; for(i=1;i<p;i++){ ans[i] = fuck[i]; mp[fuck[i]] = i; } j = p; build(1,j,1); for(i=1;i<=q;i++){ if(a[i].op=='a'){ n++; update(mp[a[i].num],1,1,j,1); if(n%2){ printf("%d\n",ans[query(n/2+1,1,j,1)]); } else{ ll temp = 0; temp += ans[query(n/2,1,j,1)]; temp += ans[query(n/2+1,1,j,1)]; double t2 = temp / 2.0; //printf("%lf\n",t2); output(t2); } } else{ if(n==0){ puts("Wrong!"); continue; } flag = 0; update(mp[a[i].num],-1,1,j,1); if(flag==1){ puts("Wrong!"); continue; } n--; if(n==0){ puts("Empty!"); continue; } if(n%2){ printf("%d\n",ans[query(n/2+1,1,j,1)]); } else{ ll temp = 0; temp += ans[query(n/2,1,j,1)]; temp += ans[query(n/2+1,1,j,1)]; double t2 = temp / 2.0; //printf("%lf\n",t2); output(t2); } } } } return 0; } /* 10 a 1 a 1000000000 a 1000000000 a -1000000000 a 500 a 60000 r 1000000000 r 1 r 500 a 3000 */
ZOJ--3612--Median【线段树+离散化】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。