Luck and Love
Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5382 Accepted Submission(s): 1344
而是我在你面前
可你却不知道我爱你
―― 张小娴
前段日子,枫冰叶子给Wiskey做了个征婚启事,聘礼达到500万哦,天哪,可是天文数字了啊,不知多少MM蜂拥而至,顿时万人空巷,连扫地的大妈都来凑热闹来了。―_―|||
由于人数太多,Wiskey实在忙不过来,就把统计的事情全交给了枫冰叶子,自己跑回家休息去了。这可够枫冰叶子忙的了,他要处理的有两类事情,一是得接受MM的报名,二是要帮Wiskey查找符合要求的MM中缘分最高值。
接下来是一个操作符C。
当操作符为‘I’时,表示有一个MM报名,后面接着一个整数,H表示身高,两个浮点数,A表示活泼度,L表示缘分值。 (100<=H<=200, 0.0<=A,L<=100.0)
当操作符为‘Q’时,后面接着四个浮点数,H1,H2表示身高区间,A1,A2表示活泼度区间,输出符合身高和活泼度要求的MM中的缘分最高值。 (100<=H1,H2<=200, 0.0<=A1,A2<=100.0)
所有输入的浮点数,均只有一位小数。
对查找不到的询问,输出-1。
8 I 160 50.5 60.0 I 165 30.0 80.5 I 166 10.0 50.0 I 170 80.5 77.5 Q 150 166 10.0 60.0 Q 166 177 10.0 50.0 I 166 40.0 99.9 Q 166 177 10.0 50.0 0
80.5 50.0 99.9
分析:
有两个区间要查找。
第一次写二维线段树,有蛮多细节要考虑的。。
二维线段树 由 母树 和 子树 组成。
母树的每个区间都有一棵树。
这里母树用高作为区间长度。子树用活泼值。然后母树和子树都有一个 max 域,用来存储最大值。
开始的时候,更新时我就只把母树的叶子节点更新了,结果查询出问题,老半天才看出来。
后来就改成 只要含有这个高度值的区间都更新。
这个题目需要解决几个问题:
1. 活泼值只到小数点后一位,所以乘上10取整就可以了。区间就成了 (0,1000)
这样可以AC , 但是有一组案例:
2 I 170 69.3 96.5 Q 144 184 38.3 69.2 0 答案 : -1
就会答案为 96.5 .。是因为 做 int(b1*10) 乘法时出现了 精度误差 本来是 383 的 变成了382 。
要加上一个 1e-6 才行。 -------学到了。。。
2. 数据中会有 A1 > A2 or H1 > H2 比较下就OK
3. 数据中还会出现 更新时 H 和 A 值一样的 就与当下的缘分值比较下大小就OK
//Accepted 1823 203MS 7552K 3221 B C++ #include <iostream> #include<cstdio> using namespace std; #define MAXN 200 const double eps=1e-6; struct node1 { int left,right; double max; }; struct node2 { int l,r; double max; node1 sub[6000]; }tree[MAXN*3]; double max(double a,double b) {return a>b?a:b;} void creat1(int fa,int root,int left,int right) { tree[fa].sub[root].left=left; tree[fa].sub[root].right=right; tree[fa].sub[root].max=0; if(left==right) return ; int mid=(left+right)>>1; creat1(fa,root<<1,left,mid); creat1(fa,root<<1|1,mid+1,right); } double insert1(int fa,int root,int pos,double val) { if(tree[fa].sub[root].left>pos||tree[fa].sub[root].right<pos) return tree[fa].sub[root].max; if(tree[fa].sub[root].left==tree[fa].sub[root].right) return tree[fa].sub[root].max=max(val,tree[fa].sub[root].max); return tree[fa].sub[root].max=max(insert1(fa,root<<1,pos,val),insert1(fa,root<<1|1,pos,val)); } double query1(int fa,int root,int left,int right) { if(tree[fa].sub[root].left>right||tree[fa].sub[root].right<left) return 0; if(tree[fa].sub[root].left>=left&&tree[fa].sub[root].right<=right) return tree[fa].sub[root].max; return max(query1(fa,root<<1,left,right),query1(fa,root<<1|1,left,right)); } void creat2(int root,int left,int right) { tree[root].l=left; tree[root].r=right; tree[root].max=0; creat1(root,1,0,1000); if(left==right) return; int mid=(left+right)>>1; creat2(root<<1,left,mid); creat2(root<<1|1,mid+1,right); } void insert2(int root,int h,int a,double vol) { insert1(root,1,a,vol); if(tree[root].l==tree[root].r) return; if(tree[root<<1].r >=h ) insert2(root<<1,h,a,vol); else insert2(root<<1|1,h,a,vol); } double query2(int root,int h1,int h2,int a1,int a2) { if(tree[root].l>h2||tree[root].r<h1) return 0; if(tree[root].l>=h1&&tree[root].r<=h2) { return query1(root,1,a1,a2); } return max(query2(root<<1,h1,h2,a1,a2),query2(root<<1|1,h1,h2,a1,a2)); } void swap(int &a,int &b) { int t=a; a=b; b=t; } int main() { int M; while(~scanf("%d",&M)&&M) { char op[2]; creat2(1,0,100); while(M--) { scanf("%s",op); if(op[0]=='I') { int h,a; double act,aff; scanf("%d%lf%lf",&h,&act,&aff); a=int((act+eps)*10); insert2(1,h-100,a,aff); } else if(op[0]=='Q') { int a1,a2; double b1,b2; scanf("%d%d%lf%lf",&a1,&a2,&b1,&b2); // cout<<"不加 "<<int(b1*10)<<" "<<int(b2*10)<<endl; // cout<<"加 "<<int((b1+eps)*10)<<" "<<int((b2+eps)*10)<<endl; int c1=int((b1+eps)*10); int c2=int((b2+eps)*10); if(a1>a2) swap(a1,a2); if(c1>c2) swap(c1,c2); double ans=query2(1,a1-100,a2-100,c1,c2); if(ans==0.0) printf("-1\n"); else printf("%.1lf\n",ans); } } } return 0; } /** 8 I 160 50.5 60.0 I 165 30.0 80.5 I 166 10.0 50.0 I 170 80.5 77.5 Q 130 120 50.5 60.1 2 //加上eps 才能过这案例! I 170 69.3 96.5 Q 144 174 38.3 69.2 0 //答案 -1 2 I 170 69.3 96.5 Q 144 174 38.3 69.2 0 **/