首页 > 代码库 > 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;}