首页 > 代码库 > Luck and Love（二维线段树）
Luck and Love（二维线段树）
Luck and Love |
| Time Limit: 10000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 54 Accepted Submission(s): 21 |
Problem Description 世界上上最远的距离不是相隔天涯海角 而是我在你面前 可你却不知道我爱你 ―― 张小娴 前段日子，枫冰叶子给Wiskey做了个征婚启事，聘礼达到500万哦，天哪，可是天文数字了啊，不知多少MM蜂拥而至，顿时万人空巷，连扫地的大妈都来凑热闹来了。―_―||| 由于人数太多，Wiskey实在忙不过来，就把统计的事情全交给了枫冰叶子，自己跑回家休息去了。这可够枫冰叶子忙的了，他要处理的有两类事情，一是得接受MM的报名，二是要帮Wiskey查找符合要求的MM中缘分最高值。 |
Input 本题有多个测试数据，第一个数字M，表示接下来有连续的M个操作，当M＝0时处理中止。 接下来是一个操作符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） 所有输入的浮点数，均只有一位小数。 |
Output 对于每一次询问操作，在一行里面输出缘分最高值，保留一位小数。 对查找不到的询问，输出-1。 |
Sample Input 8I 160 50.5 60.0I 165 30.0 80.5I 166 10.0 50.0I 170 80.5 77.5Q 150 166 10.0 60.0Q 166 177 10.0 50.0I 166 40.0 99.9Q 166 177 10.0 50.00 |
Sample Output 80.550.099.9 |
Author 威士忌 |
Source HDOJ 2007 Summer Exercise（3）- Hold by Wiskey |
Recommend 威士忌 |
/*题意：略初步思路：二位线段树,只有一位小数，×10，之后数据就可以用线段树处理#错误：少了-1的情况，wa到死*/#include<bits/stdc++.h>using namespace std;int n;char op[2];int h1,h2,h;float a,l;float a1,a2;/***********************************二维线段树模板(最大值)****************************************/#define LL long long#define INF 0x3f3f3f3fconst int N=5005;float seg[N][N<<2]; // 表示X轴Y轴；void Build_2(int l,int r,int deep,int rt) // 建y轴方向线段树(二维)；{ seg[deep][rt]=-1.0; if(l==r) return; int mid=(l+r)>>1; Build_2(l,mid,deep,rt<<1); Build_2(mid+1,r,deep,rt<<1|1);}void Build(int l,int r,int rt) // 建x轴方向线段树(一维)；{ Build_2(0,1000,rt,1); if(l==r) return; int mid=(l+r)>>1; Build(l,mid,rt<<1); Build(mid+1,r,rt<<1|1);}void Insert_2(int act,float love,int l,int r,int deep,int rt) // y轴方向更新数据；(二维){ seg[deep][rt]=max(love,seg[deep][rt]); if(l==r) return; int mid=(l+r)>>1; if(act<=mid) Insert_2(act,love,l,mid,deep,rt<<1); else Insert_2(act,love,mid+1,r,deep,rt<<1|1); seg[deep][rt]=max(seg[deep][rt<<1],seg[deep][rt<<1|1]);}void Insert(int h,int act,float love,int l,int r,int rt) // x轴,一维；{ Insert_2(act,love,0,1000,rt,1); if(l==r) return; int mid=(l+r)>>1; if(h<=mid) Insert(h,act,love,l,mid,rt<<1); else Insert(h,act,love,mid+1,r,rt<<1|1);}float Query_2(int L,int R,int l,int r,int rt,int deep) // 查询，y轴,二维；{ if(L<=l&&R>=r) return seg[deep][rt]; int mid=(l+r)>>1; if(R<=mid) return Query_2(L,R,l,mid,rt<<1,deep); else if(L>mid) return Query_2(L,R,mid+1,r,rt<<1|1,deep); else return max(Query_2(L,R,l,mid,rt<<1,deep),Query_2(L,R,mid+1,r,rt<<1|1,deep));}float Query(int h1,int h2,int L,int R,int l,int r,int rt) // x轴，一维；{ // cout<<h1<<" "<<h2<<" "<<L<<" "<<R<<endl; if(h1<=l&&h2>=r) return Query_2(L,R,0,1000,1,rt); int mid=(l+r)>>1; if(h2<=mid) return Query(h1,h2,L,R,l,mid,rt<<1); else if(h1>mid) return Query(h1,h2,L,R,mid+1,r,rt<<1|1); else return max(Query(h1,h2,L,R,l,mid,rt<<1),Query(h1,h2,L,R,mid+1,r,rt<<1|1));}/***********************************二维线段树模板(最大值)****************************************/int main(){ // freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF&&n){ Build(100,200,1); for(int i=0;i<n;i++){ scanf("%s",op); if(op[0]==‘I‘){//插入 scanf("%d%f%f",&h,&a,&l); // cout<<op[0]<<" "<<h<<" "<<a<<" "<<l<<endl; int aa=(int)(a*10); // cout<<h<<" "<<aa<<" "<<ll<<endl; Insert(h,aa,l,100,200,1); }else{//查询 scanf("%d%d%f%f",&h1,&h2,&a1,&a2); // cout<<op[0]<<" "<<h1<<" "<<h2<<" "<<a1<<" "<<a2<<endl; if(a1>a2){ float tmp=a1; a1=a2; a2=tmp; } int A1=(int)(a1*10); int A2=(int)(a2*10); if(h1>h2){ int tmp=h1; h1=h2; h2=tmp; } // cout<<H1<<" "<<H2<<" "<<A1<<" "<<A2<<endl; float res=Query(h1,h2,A1,A2,100,200,1); if(res==-1.0) puts("-1"); else printf("%.1f\n",res); } } } return 0;}
Luck and Love（二维线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。