首页 > 代码库 > hdu 1541 Stars 解题报告
hdu 1541 Stars 解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1541
题目意思:有 N 颗星星,每颗星星都有各自的等级。给出每颗星星的坐标(x, y),它的等级由所有比它低层(或者同层)的或者在它左手边的星星数决定。计算出每个等级(0 ~ n-1)的星星各有多少颗。
我只能说,题目换了一下就不会变通了,泪~~~~
星星的分布是不是很像树状数组呢~~~没错,就是树状数组题来滴!
按照题目输入,当前星星与后面的星星没有关系。所以只要把 x 之前的横坐标加起来就可以了。不过要注意树状数组是从下标 1 开始算的,而输入有可能 是 0(横坐标x = 0),所以题目中当x = 0 时,要执行 x++,相当于所有坐标右移一位,但是没有改变坐标间的相对位置。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 32000 + 5;int c[maxn], level[maxn];int lowbit(int x){ return x & (-x);}void update(int pos){ while (pos < maxn) { c[pos]++; pos += lowbit(pos); }}int sum(int x){ int s = 0; while (x > 0) { s += c[x]; x -= lowbit(x); } return s;}int main(){ int n, x, y; while (scanf("%d", &n) != EOF) { memset(c, 0, sizeof(c)); // 没了这两行会 memset(level, 0, sizeof(level)); // runtime error ! for (int i = 0; i < n; i++) { scanf("%d%d", &x, &y); level[sum(x+1)]++; // 为了防止出现x = 0的情况,所有 x 右移一位,保持横坐标相对次序不变 update(x+1); // 下标为x + 1的位置加上1 } for (int i = 0; i < n; i++) printf("%d\n", level[i]); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。