HDU 1542 Stars [树状数组]【数据结构】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1541 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Problem Description For example,look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it’s formed by three stars with a numbers 1,2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0,two stars of the level 1,one star of the level 2,and one star of the level 3. You are to write a program that will count the amounts of the stars of each level on a given map. Input Output Sample Input Sample Output Source ————————————————————. 题目大意 : 解题思路 : 仔细读题 发现y是递增的 这样的话 y值就没什么用了 我们只要维护x就可以了 维护前用桶记录一下就可以了;; 附本题代码 #include <bits/stdc++.h>
using namespace std;
/**************************************/
const int N = 50000 + 5;
#define lowbit(x) (x&(-x))
int sum[N],cnt,nnn[N];
void update(int index,int val){
for(int i=index;i<=N;i+=lowbit(i)){
sum[i]+=val;
}
}
int getSum(int index) {
int ans = 0;
for (int i = index; i>0; i -= lowbit(i))
ans += sum[i];
return ans;
}
int main()
{
while(~scanf("%d",&cnt)){
int x,y;
memset(sum,0,sizeof(sum));
memset(nnn,sizeof(nnn));
for(int i=0;i<cnt;i++){
scanf("%d%d",&x,&y);
nnn[getSum(x+1)]++;
update(x+1,1);
}
for(int i=0;i<cnt;i++){
printf("%dn",nnn[i]);
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |