首页 > 代码库 > hdu 1541 Stars 解题报告

hdu 1541 Stars 解题报告

2024-07-18 15:52:38   215人阅读

题目链接：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;}


联系
我们