首页 > 代码库 > hdu5107 K-short Problem(线段树+离散化+思维)
hdu5107 K-short Problem(线段树+离散化+思维)
题目链接:
huangjing
题意:就是给出狠点建筑的坐标和高度,然后给出很多询问,求在这个坐标右下角的第k矮的建筑。。
思路:太弱了我,这个题目从上个星期天就开始看,但是一直不会,所以只能看别人思路,因为那个k小于10,所以左右节点只取前十就可以了,但是我觉得万一不记录完全万一发生丢失怎么办,后来一想sb了,如果左右节点都取前10的话,那么根节点得到的20个值,在排序必定取到了前10啊。。。言归正传,这道题因为数据范围太大了,前对建筑和询问一起排序,按x从小到大,再按y从小到大,在按建筑优先的原则排序。所以先对坐标y进行离散化,然后建树,然后开始插入,然后对节点进行维护(只需要维护前10个值就可以了),然后这个问题就解决了。。。我觉得和cf的一个题很像。。。
ps:我这个题敲了几遍,觉得收货很大。。还有就是这题数据太弱了,直接暴力也可以过,并且跑的比线段树的快多了。。。
题目:
K-short Problem
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 366 Accepted Submission(s): 98
Problem Description
In the view of a satellite, you can see lots of tall buildings in the city, and we assume that the city‘s border is flat. Now you have observed n tall buildings in the city and recorded their position and height. Due to some mysterious reasons, you need to answer a series of queries. Each query will give you a position(x, y) and k, then you have to find out the k-th shortest building in set{(x,y)|x≤X,y≤Y }.
Input
Multiple test cases.For each test case, the first line will contain two integers n and m(0<n≤30000,0≤m≤30000 ), which represents the amount of buildings and amount of queries. Then n lines follow, contains three integers x,y,h(?1E9≤x,y≤1E9,0≤h≤1E9) indicate the building‘s position and height in each line. Then there are m lines, each with three integers x,y,k(?1E9≤x,y≤1E9,1≤k≤10) used for query.
Output
For each test case, if the k-th shortest building exists, output its height in 1 line, otherwise print "-1" (without quotes).
Sample Input
5 2 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 0 0 1 6 3 2
Sample Output
-1 2
Source
BestCoder Round #18
Recommend
heyang | We have carefully selected several similar problems for you: 5106 5103 5102 5101 5100
代码:
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=60000+10; struct Node { int x,y,id,flag,h; void init() { scanf("%d%d%d",&x,&y,&h); } }node[maxn]; struct Tree { int sum,xx[25]; }tree[maxn<<2]; int n,m,cnt,top[maxn],ans[maxn],x,cc,FB[maxn]; bool cmp(Node a,Node b) { if(a.x!=b.x) return a.x<b.x; if(a.y!=b.y) return a.y<b.y; return a.flag<b.flag; } void push_up(int dex) { int k=0; for(int i=1;i<=tree[dex<<1].sum;i++) tree[dex].xx[++k]=tree[dex<<1].xx[i]; for(int i=1;i<=tree[dex<<1|1].sum;i++) tree[dex].xx[++k]=tree[dex<<1|1].xx[i]; tree[dex].sum=k; sort(tree[dex].xx+1,tree[dex].xx+1+tree[dex].sum); if(k>10) tree[dex].sum=10; } void buildtree(int dex,int l,int r) { tree[dex].sum=0; memset(tree[dex].xx,0,sizeof(tree[dex].xx)); if(l==r) return; int mid=(l+r)>>1; buildtree(dex<<1,l,mid); buildtree(dex<<1|1,mid+1,r); } void Update(int dex,int l,int r,int pos,int val) { if(l==r) { tree[dex].xx[++tree[dex].sum]=val; sort(tree[dex].xx+1,tree[dex].xx+1+tree[dex].sum); if(tree[dex].sum>10) tree[dex].sum=10; return; } int mid=(l+r)>>1; if(pos<=mid) Update(dex<<1,l,mid,pos,val); else Update(dex<<1|1,mid+1,r,pos,val); push_up(dex); } void Query(int dex,int l,int r,int L,int R) { if(L<=l&&R>=r) { for(int i=1;i<=tree[dex].sum;i++) FB[++cc]=tree[dex].xx[i]; sort(FB+1,FB+1+cc); if(cc>10) cc=10; return; } int mid=(l+r)>>1; if(L<=mid) Query(dex<<1,l,mid,L,R); if(R>mid) Query(dex<<1|1,mid+1,r,L,R); } int main() { while(~scanf("%d%d",&n,&m)) { cnt=0; for(int i=1;i<=n+m;i++) { node[i].init(); node[i].id=i; top[++cnt]=node[i].y; if(i<=n) node[i].flag=0; else node[i].flag=1; } sort(node+1,node+1+n+m,cmp); sort(top+1,top+1+cnt); x=unique(top+1,top+1+cnt)-(top+1); buildtree(1,1,x); for(int i=1;i<=n+m;i++) { int pos=lower_bound(top+1,top+1+x,node[i].y)-top; if(!node[i].flag) Update(1,1,x,pos,node[i].h); else { cc=0; Query(1,1,x,1,pos); if(cc<node[i].h) ans[node[i].id]=-1; else ans[node[i].id]=FB[node[i].h]; } } for(int i=n+1;i<=n+m;i++) printf("%d\n",ans[i]); } return 0; }
hdu5107 K-short Problem(线段树+离散化+思维)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。