链接:
http://poj.org/problem?id=2352
题目大意:
在坐标上有n个星星,如果某个星星坐标为(x, y), 它的左下位置为:(x0,y0),x0<=x 且y0<=y。如果左下位置有a个星星,就表示这个星星属于level x
按照y递增,如果y相同则x递增的顺序给出n个星星,求出所有level水平的数量。
分析与总结:
因为输入是按照按照y递增,如果y相同则x递增的顺序给出的, 所以,对于第i颗星星,它的level就是之前出现过的星星中,横坐标x小于等于i星横坐标的那些星星的总数量(前面的y一定比后面的y小)。
所以,需要找到一种数据结构来记录所有星星的x值,方便的求出所有值为0~x的星星总数量。
树状数组和线段树都是很适合处理这种问题。
代码:
1. 树状数组
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 32005;
int c[MAXN],level[MAXN],n;
int lowbit(int x){return x & (-x);}
// 求前n项的和
int sum(int n){
int sum = 0;
while(n > 0){
sum += c[n];
n -= lowbit(n);
}
return sum;
}
// 增加某个元素的大小
void add(int x){
while(x <= MAXN){
++c[x];
x += lowbit(x);
}
}
int main(){
int n,x,y;
while(~scanf("%d",&n)){
memset(level, 0, sizeof(level));
memset(c, 0, sizeof(c));
for(int i=0; i<n; ++i) {
scanf("%d%d",&x,&y);
++x;
level[sum(x)]++;
add(x);
}
for(int i=0; i<n; ++i)
printf("%d\n",level[i]);
}
return 0;
}
2. 线段树
#include<iostream>
#include<cstdio>
#include<cstring>
#define mid ((left+right)>>1)
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
using namespace std;
const int MAXN = 32005;
int sum[MAXN<<2],level[MAXN<<2];
void update(int rt,int left,int right,int data){
++sum[rt];
if(left==right) return;
if(data <= mid) update(lson,data);
else update(rson,data);
}
int query(int rt,int left,int right,int l,int r){
if(left==l && right==r) {
return sum[rt];
}
int m = mid;
if(r <= m) return query(lson,l,r);
else if(l > m) return query(rson,l,r);
else return query(lson,l,m)+query(rson,m+1,r);
}
int main(){
int n,x,y;
while(~scanf("%d",&n)){
memset(sum, 0, sizeof(sum));
memset(level, 0, sizeof(level));
for(int i=0; i<n; ++i){
scanf("%d%d",&x,&y);
++x;
++level[query(1,1,MAXN,1,x)];
update(1,1,MAXN,x);
}
for(int i=0; i<n; ++i)
printf("%d\n",level[i]);
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1746750
NULL 博文链接:https://128kj.iteye.com/blog/1747400
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
线段树、树状数组算法入门 加 poj解题报告 pdf文档
poj 2482 Stars in Your Window.md
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
NULL 博文链接:https://128kj.iteye.com/blog/1745671
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and ...
NULL 博文链接:https://128kj.iteye.com/blog/1739733
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1739064
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
poj 2763 程序 线段树 LCA 2000MS AC
POJ题解 个人写法 线段树每个人都不一样