题解 P1428 【小鱼比可爱】

· · 题解

数据有点水先放一个水点的代码，不水的思路放后面

既然标签都写了树状数组~那就用树状数组写就好了。。。

具体树状数组是啥~不知道的同学可以查一下。。大概的意思是用数组的和做出一个树

大概的思路就是A数组表示每种数有多少个

比如数据是 4 4 3 2 1 那么a[4] = 2,a[3] = 1,a[2]=1,a[1] =1

然后每次只需要找一下对应的C数组就好了

具体模拟一下样例吧

4 3 0 5 1 2

第一步：输入4 此时a数组为 0 0 0 0 1 0 0 0 ... （有一个4，所以a[4] = 1）然后计算一下a[0]+a[1]+a[2]+a[3]=0，然后第一个结果就是0

第二步：输入3 此时a数组为 0 0 0 1 1 0 0 0 ... 计算一下a[0]+a[1]+a[2]=0，输出0

第三步：输入0 此时a数组为 1 0 0 1 1 0 0 0 ... 输出0

第四步：输入5 此时a数组为 1 0 0 1 1 0 0 0 ... 计算a[0]+...+a[4] = 3，输出3

.... 所以结果就出来了

但是树状数组再操作的时候不对原来的a数组操作，而是对求和的c数组进行操作，而且C数组的第一位不能为0，所以把角标往后窜一位。。于是就变成了

a[3]代表有几个2 ，a[4]代表有几个3。。。

那上边的第二步来举例，就变成 输入3，之后a数组就是 0 0 0 0 1 1 0 0....计算计算一下a[1]+a[2]+a[3]=0，输出0

所以每次输入x，结果就是sum(x), 然后维护一遍树就可以了。。（输入3，所以a[4]要加1， 于是就变成了add(x+1)）

代码如下

#include<stdio.h>
int n;
int treearray[101];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    while (x <= 100)
    {
        treearray[x]++;
        x += lowbit(x);
    }
}
int sum(int x)
{
    int ans = 0;
    while (x > 0)
    {
        ans += treearray[x];
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    int i;
    int x;
    for (i = 0; i < 101; i++)
    {
        treearray[i] = 0;
    }
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d", &x);
//这是排格式。。。
        if (i == 0)
            printf("%d", sum(x));//每次输入一个值，计算他之前的和
        else
            printf(" %d", sum(x));
        add(x+1);
    }
    printf("\n");
    return 0;
}

好吧~有的人可能会问 大哥 你这个数据如果我输入是99999999，难道你要开这么大的空间吗。。。 是的。。这个就是开头说的数据水过的问题。。

对于这个问题，解决方案是~~先进行一次快排，~（千万别用n^2的排序。。。那样的话你还不如直接写俩循环做呢。。）

排序完之后重新赋值，根据大小把值都变成1~n的数，然后再进行上面的操作就好了。。