Binary Indexed Tree 分类： ACM TYPE 2014-08-29 13:08 99人阅读评论(0) 收藏

    #include<iostream>

    #include<cstring>

    #include<cstdio>

    using namespace std;

    int n, m;

    int num[100005];

    int front(int x)

    {

        return x&(-x);

    }

    int update(int x,int k)

    {

        while(x<=n)

        {

            num[x]+=k;

            x+=front(x);

        }

        return 1;

    }

    int sum(int x)

    {

        int s = 0;

        while(x>0)

        {

            s+=num[x];

            x-=front(x);

        }

        return s;

    }

    int main()

    {

        int a, b, c;

        int cur[5005];

        while(scanf("%d",&n)!=EOF)

        {

            memset(num,0,sizeof(num));

            memset(cur,0,sizeof(cur));

            b = 0;

            for(int i=1;i<=n;i++)

            {

                scanf("%d",&cur[i]);

                cur[i]++;

                b+=(i-sum(cur[i])-1);

                update(cur[i],1);

            }

            c = b;

            for(int i=1;i<=n;i++)

            {

                b = b + (n-cur[i] +1 ) - cur[i];

                c=b<c?b:c;

            }

            printf("%d\n",c);

        }

        return 0;

    }

Code From Hdu 1394

巴特西

Binary Indexed Tree 分类： ACM TYPE 2014-08-29 13:08 99人阅读评论(0) 收藏

最新文章

热门文章

巴特西

Binary Indexed Tree 分类： ACM TYPE 2014-08-29 13:08 99人阅读 评论(0) 收藏

最新文章

热门文章

Binary Indexed Tree 分类： ACM TYPE 2014-08-29 13:08 99人阅读评论(0) 收藏